clean python solution, linear time, constant space


  • 0
    I

    First, partition the lists into 2 using the fast and slow pointer method.
    Then, reverse the second list
    Then, just need to stitch them together. When partitioning, need to pay close attention to how to cut it if the fast pointer is None or not, see the partition_lists() subroutine.

    class Solution(object):
        def partition_lists(self, head):
            slow = head
            fast = head
            prev = None
            
            while fast and fast.next:
                prev = slow
                slow = slow.next
                fast = fast.next.next
                
            list1 = head
            list2 = None
            if not fast:
                list2 = slow
                prev.next = None
            else:
                list2 = slow.next
                slow.next = None
                
            return list1, list2
            
        def reverse_list(self, head):
            prev = None
            curr = head
            
            while curr:
                temp = curr.next
                curr.next = prev
                prev = curr
                curr = temp
                
            head = prev
            return head
        
        def reorderList(self, head):
            """
            :type head: ListNode
            :rtype: void Do not return anything, modify head in-place instead.
            """
            if not head:
                return 
            
            list1, list2 = self.partition_lists(head)
            list2 = self.reverse_list(list2)
            
            while list1 and list2:
                temp = list2.next
                list2.next = None
                
                temp2 = list1.next
                list1.next = list2
                list2.next = temp2
                
                list2 = temp
                list1 = temp2

Log in to reply
 

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