Reorder List

Given a singly linked list L: L0→ L1→ … → Ln-1→ Ln

reorder it to: L0→ Ln→ L1→ Ln-1→ L2→ Ln-2→ …

Example

Given1->2->3->4->null, reorder it to1->4->2->3->null.

Solution: 1. Divide to two list;

            2. Reverse the second list.

            3. Combine two list.

public void reorderList(ListNode head) { 
    if(head == null || head.next == null) {
        return ;
    }
    ListNode slow = head, fast = head;
    while(fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    ListNode p1 = head, p2 = slow.next;
    slow.next = null;
    p2 = reverse(p2);
    while(p2 != null) {
        ListNode post1 = p1.next;
        ListNode post2 = p2.next;
        p1.next = p2;
        p2.next = post1;
        p1 = post1;
        p2 = post2;
    }
}
public ListNode reverse(ListNode head) {
    ListNode pre = null;
    while(head != null) {
        ListNode second = head.next;
        head.next = pre;
        pre = head;
        head = second;
    }
    return pre;
}