Leetcode: Reorder List

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-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}.

Understand the problem:
The problem is not that straight-forward. It is not reorder the linked list in reverse order. It is like order from both ends. Also note that the problem requires do this in-place without altering the node's values. That means we are not allowed to create another linked list to store the result. 
For e.g. for {1,2,3,4,5,6,7} would be reordered as : {1,7,2,6,3,5,4}
{1,2,3,4,5,6} would be reordered as {1,6,2,5,3,4}


Solution:
From the examples given above, it is not hard to find out the solution could have three steps:
1. Find the middle point of the linked list (use slow-fast pointers)
2. Cut the list into halves, and reverse the second list
3. Merge two lists together.

Code (Java):

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public void reorderList(ListNode head) {
        if (head  == null || head.next == null || head.next.next == null) return;
        
        // STEP 1: Find the middle point of the linked list, use fast-slow pointers
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast != null && fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode secondHead = slow.next;
        slow.next = null; //truncate the first half
        
        // STEP 2: Reverse the second list
        ListNode prev = secondHead;
        ListNode curr = secondHead.next;
        while (curr != null) {
            ListNode temp = curr.next;
            curr.next = prev;
            prev = curr;
            curr = temp;
        }
        // setup the new head
        secondHead.next = null;
        secondHead = prev;
        
        
        // STEP 3: Merge the two lists together
        ListNode p1 = head;
        ListNode p2 = secondHead;
        
        while (p2 != null) {
            ListNode temp1 = p1.next;
            ListNode temp2 = p2.next;
            p1.next = p2;
            p2.next = temp1;
            p1 = temp1;
            p2 = temp2;
        }
        if (p1 != null) p1.next = null; //tail pointer
    }
}

Discussion:
Now let's analyze the solution. The first step of finding the midpoint takes O(n) time since it traverse the list once. In the second step, it reorder the second half of the list in reverse order, which takes O(n/2) time. In the third step, it merged two linked list together, so the complexity is O(n). Overall, the time complexity is bounded by O(n).


Summary:
The problem looks quite wired, but the take away message is the cutting down problems can be used into any other problems. In this post, we learned:
1. How to find a middle point of a linked list, using fast-slow pointer
2. How to reverse a linked list
3. How to merge two linked list together.