Reorder List

Source

LintCode 99

LeetCode 143

Problem

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.

Example

Given 1->2->3->4->null, reorder it to 1->4->2->3->null.

Solution

public void reorderList(ListNode head) {  
    if (head == null) return;

    // First find the mid point
    ListNode slow = head;
    ListNode fast = head;

    while(fast.next != null && fast.next.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }

    // reverse the second half
    ListNode secondHalfHead = null;
    slow = slow.next;
    while (slow != null) {
        ListNode next = slow.next;
        slow.next = secondHalfHead;
        secondHalfHead = slow;
        slow = next;
    }

    // Start to merge two lists
    fast = head;
    slow = secondHalfHead;

    while (slow != null) {
        ListNode next = fast.next;
        ListNode secondHalfNext = slow.next;
        fast.next = slow;
        slow.next = next;
        slow = secondHalfNext;
        fast = next;
    }
    fast.next = null;
}