Problem

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

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

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

思路

1. find the middle node
2. split the list into two halves
3. reverse list2
4. merge two list

    public void reorderList(ListNode head) {  
        if (head == null || head.next == null) {
            return;
        }
        // split into two lists
        ListNode mid = findMid(head);
        ListNode l2 = mid.next;
        mid.next = null;

        // reverse l2
        l2 = reverseList(l2);

        // merge two lists
        ListNode l1 = head.next;
        ListNode curt = head;
        while (l1 != null && l2 != null) {
            curt.next = l2;
            l2 = l2.next;
            curt = curt.next;
            curt.next = l1;
            l1 = l1.next;
            curt = curt.next;
        }
        if (l1 != null) {
            curt.next = l1;
        }
        if (l2 != null) {
            curt.next = l2;
        }
    }

    private ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curt = head;

        while (curt != null) {
            ListNode temp = curt.next;
            curt.next = prev;
            prev = curt;
            curt = temp;
        }

        return prev;
    }

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