Still simple. 3 steps to do the task: cut, reverse and merge. Concerning the cut process, we can use the slow and fast pointers-- they are really useful.
Solution:
# T:O(n) S:O(1) class Solution: # @param head, a ListNode # @return nothing def reorderList(self, head): if head == None or head.next == None: return fast, slow, prev = head, head, None while fast != None and fast.next != None: fast, slow, prev = fast.next.next, slow.next, slow current, prev.next, prev = slow, None, None while current != None: current.next, prev, current = prev, current, current.next l1, l2 = head, prev dummy = ListNode(0) current = dummy while l1 != None and l2 != None: current.next, current, l1 = l1, l1, l1.next current.next, current, l2 = l2, l2, l2.next returnRun Time: 168 ms
No comments:
Post a Comment