[LeetCode 143] Reorder List

Question

link

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}.

Stats

Adjusted Difficulty	4
Time to use	--------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is a difficult question to think.

I first solved it with an stack which stores the second half nodes. It works. However, IT IS NOT A IN-PLACE SOLUTION, thus it’s wrong.

Eventually I did not solve it.

There is only one standard solution from the Internet. This blog explains it.

1. Break list in the middle to two lists (use fast & slow pointers)
2. Reverse the order of the second list
3. Merge two list back together

Simple, right? Because of the nature of linked list, a lot of things can be done in-place, so we need not use any other data strucutres.

Solution

The code is a bit lengthy and difficult to write. It took me a while, but passed in 1 go.

Code

First, code written by me

public void reorderList(ListNode head) {
    if (head == null || head.next == null) {
        return;
    }
    ListNode slow = head, fast = head;
    while (fast != null) {
        if (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        else {
            fast = null;
        }
    }
    // if length = 2, slow point to 1st
    // if length = 3, slow point to 2nd
    // if length = 4, slow point to 2nd
    ListNode secondHalf = slow.next;
    slow.next = null;
    // now reverse secondHalf
    ListNode p = secondHalf;
    while (p.next != null) {
        ListNode tail = p.next.next;
        p.next.next = secondHalf;
        secondHalf = p.next;
        p.next = tail;
    }
    // now merge 2 list: head and secondHalf
    ListNode a = head, b = secondHalf;
    while (a != null && b != null) {
        ListNode temp1 = a.next;
        ListNode temp2 = b.next;
        a.next = b;
        b.next = temp1;
        a = temp1;
        b = temp2;
    }
}

Second, code written by someone

public void reorderList(ListNode head) {
    // IMPORTANT: Please reset any member data you declared, as
    // the same Solution instance will be reused for each test case.
    if (head == null || head.next == null) return;
    ListNode fast = head;
    ListNode slow = head;
    while(fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    ListNode reverseHead = slow.next;           // find the second half of list
    slow.next = null;                           // make first half end point to null
    reverseHead = reverse(reverseHead);         // reverse second half
    ListNode cur = head;
    while(reverseHead != null) {                // link together
        ListNode tmp = reverseHead.next;
        reverseHead.next = cur.next;
        cur.next = reverseHead;
        cur = cur.next.next;
        reverseHead = tmp;
    }
}
private ListNode reverse(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode prev = new ListNode(0);
    prev.next = head;
    head = prev;
    ListNode cur = prev.next;
    while(cur.next != null) {
        ListNode tmp = cur.next;
        cur.next = tmp.next;
        tmp.next = prev.next;
        prev.next = tmp;
    }
    return prev.next;
}