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

Analysis

• 对于list：
  • 找中点（利用slow和fast）
  • 反转后面一半链表（参考reverse linked list）
  • 穿插前后链表(参考merge 2 linked list)
• 特殊情况分析：
  • 奇偶分析
  • {1,2,3,4,5}->{1,5,2,4,3} {1,2} {5,4,3} merge-{1,5,2,4,3}
  • 短链表

Code

Reference

public class Solution {
    public void reorderList(ListNode head) {
        if (head==null || head.next==null || head.next.next==null) {return;}
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        //find mid point
        //afte following code, for {1,2,3,4} or {1,2,3,4,5}, slow points to 2/3
        //if slow and fast both initialize to head, after code, slow points to 3/3
        //这道题需要处理中间前一位的node，所以用第一种initialize方法
        ListNode fast = head.next, slow = head;
        while (fast !=null && fast.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        //定义新的头，断开之前链接
        ListNode rhead = slow.next;
        slow.next = null;

        //reverse 2nd half, need to remember!
        //temp 用来存储后面还没有reverse的nodes；prev指向的是之前已经reverse的nodes；每一次把head指向的node放到已经reverse的prev前面去；prev更新到新的head；head更新到temp。
        ListNode prev = null;
        while (rhead!=null){
            ListNode temp = rhead.next;
            rhead.next = prev;
            prev = rhead;
            rhead = temp;
        }

        //merge 2 lists
        rhead = prev;
        ListNode lhead = head;
        while (lhead !=null && rhead !=null){
            ListNode temp1 = lhead.next;
            lhead.next = rhead;
            rhead = rhead.next;
            lhead.next.next = temp1;
            lhead = temp1;
        }

    }
}

Note

• 找中点，reverse以及merge都是经典的需要掌握的！

Reference

yuanbin