143. Reorder List

Problem:

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

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

Example 2:

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

05/02/2018 update:
这道题做完了，感觉linked list功力又上一层。把这一遍刷linked lsit总结的东西都用上了。所以在merge的时候想出来了最易读，效率最高点的方法。beat 100%。

Find mid和parlindrome list一样 fast 从head.next开始。mid.next = null是我自己想出来的。因为reverse过后，mid.next实际上还是指向之前的mid.next,要重构linked list必须把它指向null。

在merge的时候做法比较直接。head.next 指向secHead, secHead.next 指向 head.next, head.next和secHead.next会丢失，更新，所以需要先cache他们。

while条件只判断secHead != null就行了，因为secHead.length <= head.length。

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

        ListNode mid = findMid(head);
        ListNode secHead = reverse(mid.next);
        mid.next = null;
        ListNode ite =  head;
        while (secHead != null) {
            ListNode temp1 = ite.next;
            ListNode temp2 = secHead.next;
            ite.next = secHead;
            secHead.next = temp1;
            ite = temp1;
            secHead = temp2;
        }
    }
    // because prev is null, so the tail of reversed list is null
    private ListNode reverse(ListNode head) {
        ListNode prev = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    private ListNode findMid(ListNode head) {
        ListNode slow = head, fast = head.next;
        // find mid
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

}

--------------------------------------------------------------------------------------------------------------------------
Update 12/28/2017

Pay attention to the corner case head.next == null. 用一个额外的dummy node来辅助merge 比直接merge到其中一个node容易实现得多。

-----------------------------------------------

思路：

思路很直接：先找到mid， 然后reverse后面一半，最后merge。实现起来对我来说很有难度，linked list操作不熟练。

实现：

以1->2->3->4->null为例。

求mid: 快指针和慢指针。需要记录mid前面那个节点，然后赋值null给断掉。现在就有2个list，1->2-null，和3->4->null。

reverse 第二个list： 4->3->null。

merge 2个list:

 private void merge(ListNode l1, ListNode l2) {  
     while (l1 != null) {  
     ListNode n1 = l1.next, n2 = l2.next;  
     l1.next = l2;  
     if (n1 == null)  
      break;  
     l2.next = n1;  
     l1 = n1;  
     l2 = n2;  
    }  
   }