Python in place solution with comments (two pointers).

  • 1

    For linked list 1->2->3->4-5, the code first makes the list to be 1->2->3->4<-5 and 4->None, then make 3->None, for even number linked list: 1->2->3->4, make first 1->2->3<-4 and 3->None, and lastly do not forget to make 2->None.

    def reorderList(self, head):
        if not head:
        # ensure the first part has the same or one more node
        fast, slow =, head
        while fast and
            fast =
            slow =
        # reverse the second half
        p = = None
        node = None
        while p:
            nxt =
   = node
            node = p
            p = nxt
        # combine head part and node part
        p = head
        while node:
            tmp =
   = node
            p = #p =
            node = tmp

Log in to reply

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