Python with comments, O(n) time, O(1) space


  • 0

    Basically we need 3 steps to solve this problem. First, use two pointers to break original linked list into two equal length parts (exactly equals when we have even listnode, differs 1 when odd cases). Then, reverse the latter part. Finally, reconstruct the whole linked list.

    Since the length of latter part is always equal or smaller than the other one, we only need to examine whether the pointer of latter part meets the end in the last step.

    class Solution(object):
        def reorderList(self, head):
            """
            :type head: ListNode
            :rtype: void Do not return anything, modify head in-place instead.
            """
            if not head: return head
            
            # break linked list into two "equal" length parts
            slow = fast = head
            while fast and fast.next:
                slow = slow.next
                fast = fast.next.next
            p = slow.next
            slow.next = pre = None
            
            # reverse the latter part
            while p:
                p.next, pre, p = pre, p, p.next
                
            # reconstruct the whole linked list
            p = head
            while pre:
                p.next, pre.next, p, pre = pre, p.next, p.next, pre.next
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.