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

先找中点，把原来的list拆为两个，把后半截reverse，然后再把两个list一个一个交替连起来

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if(head == null){
            return;
        }
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        
        //find mid point;
        ListNode slow = dummy,fast = dummy;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        
        //slow now is mid point;
        
        //got the second half head;
        ListNode head2 = reverse(slow);
        
        slow.next = null;
        
        connect(dummy.next,head2);
        
        
    }
    
    public ListNode connect(ListNode head1, ListNode head2){
        ListNode dummy = new ListNode(-1);
        dummy.next = head1;
        
        ListNode tail = dummy;
        
        while(head1 != null && head2 != null){
            tail.next = head1;
            tail = head1;
            head1 = tail.next;
            tail.next = head2;
            tail = head2;
            head2 = tail.next;
        }
        
        if(head1 != null){
            tail.next = head1;
        }
        
        if(head2 != null){
            tail.next = head2;
        }
                
        return dummy.next;
    }
    
    public ListNode reverse(ListNode node){
        if(node == null || node.next == null){
            return null;
        }
        
        ListNode cur = node.next;
        ListNode pre = null, next = null;
        
        while(cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        
        return pre;
    }
    
    
    
}