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}.
public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        ListNode beforeMid = findNodeBeforeMiddle (head);
        ListNode mid = reverse(beforeMid.next);
        beforeMid.next = null;
        //Now we have 2 LinkedList: the first half & the last half
        ListNode header = new ListNode (0);
        ListNode cur = header;
        //the first half would not be shorter than the second half
        while (mid != null) {
            ListNode hn = head.next;
            ListNode mn = mid.next;

            head.next = mid;
            cur.next = head;

            head = hn;
            mid = mn;
            cur = cur.next.next;
        }

        if(head != null)
            cur.next = head;
        if(mid != null)
            cur.next = mid;

    }
    private ListNode reverse (ListNode head) {
        ListNode newHead = null;
        while (head != null) {
            ListNode temp = head.next;
            head.next = newHead;
            newHead = head;
            head = temp;
        }
        return newHead;
    }

    private ListNode findNodeBeforeMiddle (ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s