clean python solution, linear time, constant space

  • 0

    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
                prev = slow
                slow =
                fast =
            list1 = head
            list2 = None
            if not fast:
                list2 = slow
       = None
                list2 =
       = None
            return list1, list2
        def reverse_list(self, head):
            prev = None
            curr = head
            while curr:
                temp =
       = 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:
            list1, list2 = self.partition_lists(head)
            list2 = self.reverse_list(list2)
            while list1 and list2:
                temp =
       = None
                temp2 =
       = list2
       = 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.