[LeetCode] Reorder List

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-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}.

解题思路：
1，找出中间位置的element，将linkedlist分为两半
2，反转后半部分的linkedlist
3，将2部分的linkedlist合成

注意：在找出median的element的时候，我用了最基本的方法，统计出element的总数，然后count/2. 这样就会重复遍历list. 可以设置2个指针，一个每次走一步，另一个每次走2步，走到2步为null的时候，走一步的指针就指向的为中间的element


Java Code:

public void reorderList(ListNode head) {
        int count = 0;
        ListNode p = head;
        
        while( p != null){
            p = p.next;
            count++;
        }
        
        if(count < 3) return;
        
        //find the median element starting with p
        ListNode prev = head;
        p = head;
        int i = 0;
        while( p != null && i <= count/2){
            i++;
            prev = p;
            p = p.next;
        }
        
        //reverse the after half linkedList
        prev.next = null;
        prev = prev.next;
        
        while(p != null){
               ListNode tmp = p;
               p = p.next;
               tmp.next = prev;
               prev = tmp;
        }
        
        p = prev;
        prev = head;
        //merge the two half linkedlist 
        while(p != null && prev != null){
            ListNode tmp = p;
            p = p.next;
            tmp.next = prev.next;
            prev.next = tmp;
            prev = tmp.next;
        }
        
    }