A python solution O(n) time, O(1) space


  • 31
    R
    # Splits in place a list in two halves, the first half is >= in size than the second.
    # @return A tuple containing the heads of the two halves
    def _splitList(head):
        fast = head
        slow = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next
            fast = fast.next
    
        middle = slow.next
        slow.next = None
    
        return head, middle
    
    # Reverses in place a list.
    # @return Returns the head of the new reversed list
    def _reverseList(head):
    
      last = None
      currentNode = head
    
      while currentNode:
        nextNode = currentNode.next
        currentNode.next = last
        last = currentNode
        currentNode = nextNode
    
      return last
    
    # Merges in place two lists
    # @return The newly merged list.
    def _mergeLists(a, b):
    
        tail = a
        head = a
    
        a = a.next
        while b:
            tail.next = b
            tail = tail.next
            b = b.next
            if a:
                a, b = b, a
                
        return head
    
    
    class Solution:
    
        # @param head, a ListNode
        # @return nothing
        def reorderList(self, head):
    
            if not head or not head.next:
                return
    
            a, b = _splitList(head)
            b = _reverseList(b)
            head = _mergeLists(a, b)

  • 23
    C

    A concise version

    def reorderList(self, head):
        if not head:
            return
            
        # find the mid point
        slow = fast = head 
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
    
        # reverse the second half in-place
        pre, node = None, slow
        while node:
            pre, node.next, node = node, pre, node.next
        
        # Merge in-place; Note : the last node of "first" and "second" are the same
        first, second = head, pre
        while second.next:
            first.next, first = second, first.next
            second.next, second = first, second.next
        return 

  • 0
    D

    I came up with a very similar code, but in the second while loop I wrote pre, node, node.next = node, node.next, pre instead of pre, node.next, node = node, pre, node.next. Why does switching the order of assignment matter here? I thought Python evaluated the entire right side before doing any assignment at all?


  • 1
    C

    You are right that the right hand side would be evaluated first. But then it will assign these value/objects to those on the left hand side one by one. In your code, the original node.next will be assign to the new node first, and then the original pre will be assigned to the NEW node.next since node has already been assigned to a new object.


  • 0
    M

    @cmc Elegant Solution :astonished:


  • 1
    A

    @cmc

    Note : the last node of "first" and "second" are the same

    The note is valid when the linked list has "odd" number of nodes, but not true when there are even number of nodes.


  • 0
    W

    @cmc said in A python solution O(n) time, O(1) space:

    A concise version

    def reorderList(self, head):
        if not head:
            return
            
        # find the mid point
        slow = fast = head 
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
    
        # reverse the second half in-place
        pre, node = None, slow
        while node:
            pre, node.next, node = node, pre, node.next
        
        # Merge in-place; Note : the last node of "first" and "second" are the same
        first, second = head, pre
        while second.next:
            first.next, first = second, first.next
            second.next, second = first, second.next
        return 
    

    this is a nice one


  • 1

    @cmc said in A python solution O(n) time, O(1) space:

    first.next, first = second, first.next
    second.next, second = first, second.next

    I tried to change

    first.next, first = second, first.next
    second.next, second = first, second.next
    
    to
    
               next = first.next
                first.next = second
                first = next
                
                next2 = second.next
                second.next = first
                second = next2
    
    

    it is more readable hahaha


  • 0
    G

    Upvoted. "the first half is >= in size than the second" is the key. These sort of off-by-one issue is the most confusing part in linked list questions.


  • 0
    B

    To clarify about the line pre, node.next, node = node, pre, node.next. We need to understand that the right hand side will be evaluated first before the assignment, and the left hand side will be assigned values one by one, from left to right. (First pre, and then node and the last node.next)

    Let's say we have a linked list 1 -> 2 -> 3 -> 4 -> 5. After we found the mid point, we have pre = None, node = 3 -> 4 -> 5

    Before we run the multiple assignment:
    pre, node.next, node = node, pre, node.next
    the original values on the right hand side are: node: 3 -> 4 -> 5, pre: None, node.next: 4 -> 5

    And then new pre will store the reference to original node: 3->4->5, and then node.next will refer to original pre: None, which means after these two assignments, we have new pre: 3->None.

    At last we assign the original node.next: 4->5 to new node, so the new node has 4->5.

    In the next iteration, the right hand side will have node: 4->5, pre:3->None, node.next: 5->None. Then the new pre is going to have 4->5 first, then the old pre will replace the tail of new pre, which makes it 4->3. And new node would have node: 5.

    Same as the next iteration.

    So this line basically takes out each value in the linked list one by one in order, and then treat each one as tail and append it to the new one.


  • 0
    X

    any people knows that what's the meaning of second number of (128ms,0.28) in Accepted Solutions Runtime Distribution???


Log in to reply
 

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