[Leetcode] 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}.

比较综合的链表题，主要考察了链表的partition，reverse以及merge，基本上是比较模块化的一道题，注意处理不要弄到null或者reverse的时候弄出环来即可。

public void reorderList(ListNode head) {
        ListNode temp = head;
        int cnt = 0;
        while(temp != null) {
            cnt++; temp = temp.next;
        }
        if(cnt <= 2) return;
        
        int hal = cnt / 2;
        ListNode dum1 = new ListNode(0);
        ListNode dum2 = new ListNode(0);
        dum1.next = head;
        temp = head;
        while(hal > 1) {
            hal--; temp = temp.next;
        }
        dum2.next = temp.next;
        temp.next = null; // safe
        
        ListNode temp1 = dum2.next, temp2 = dum2.next; // reverse the second half
        dum2.next = null; // safe
        while(temp1 != null) {
            temp2 = temp1.next;
            temp1.next = dum2.next;
            dum2.next = temp1;
            temp1 = temp2;
        }
        
        ListNode dummy = new ListNode(0); // merge the two half
        temp = dummy;
        temp1 = dum1.next; temp2 = dum2.next;
        while(temp1 != null && temp2 != null) {
            temp.next = temp1;
            temp = temp.next;
            temp1 = temp1.next;
            temp.next = temp2;
            temp = temp.next;
            temp2 = temp2.next;
        }
        temp.next = temp2;
        
        head = dummy.next;
    }