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

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.

这个题目其实柔和了快慢指针找中点，reverse linkedlist 以及merge的技巧

/**
 * 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 middle = findMiddle(head);
        ListNode reverse = reverseList(middle.next);
        middle.next = null;
        mergeList(head, reverse);
    }

    public void mergeList(ListNode left, ListNode right) {
        ListNode head = new ListNode(-1);
        while(right != null){
            head.next = left;
            left = left.next;
            head = head.next;
            head.next = right;
            right = right.next;
            head = head.next;
        }
        if (left != null) {
            head.next = left;
        }
    }

    public ListNode reverseList(ListNode node) {
        if (node == null) return node;
        ListNode pre = null;
        while (node != null) {
            ListNode temp = node.next;
            node.next = pre;
            pre = node;
            node = temp;
        }
        return pre;
    }

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