Leetcode 143: Reorder List

https://leetcode.com/problems/reorder-list/

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…

You must do this in-place without altering the nodes’ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

 

Code

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        if not head or not head.next:
            return 
        
        # find the middle point, where p1 will finally land.
        p1 = p2 = head        # p1: fast pointer, p2: slow pointer
        while p2.next and p2.next.next:
            p2 = p2.next.next
            p1 = p1.next
        
        p3 = p1.next
        head2 = None
        p1.next = None
        
        # reverse the latter part
        while p3:
            next = p3.next
            p3.next = head2
            head2 = p3
            p3 = next
        
        # the first part has at least one more element than the second part
        while head:
            next1 = head.next
            head.next = head2
            if head2:
                next2 = head2.next
                head2.next = next1
            head = next1
            head2 = next2

 

Idea

There are three steps:

1. use a slow pointer and a fast pointer to find the middle point of the linked list. The middle point will split the linked list into two parts.
2. Reverse the second part of the linked list.
3. Merge the two parts.