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.
难度：medium
题目：给定一单链表 L: L0→L1→…→Ln-1→Ln, 重新排序为: L0→Ln→L1→Ln-1→L2→Ln-2→…
思路：先使用快慢指针一个一次走一步，另一个一次走两步，找出中间点。再使用头插法处理后半段，最后合并两链表。
Runtime: 2 ms, faster than 99.27% of Java online submissions for Reorder List.
Memory Usage: 40.4 MB, less than 100.00% of Java online submissions for Reorder 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 (null == head) { return; } ListNode oneStepPtr = head, twoStepsPtr = head, midPtr = oneStepPtr; while (twoStepsPtr != null) { midPtr = oneStepPtr; oneStepPtr = oneStepPtr.next; twoStepsPtr = (null == twoStepsPtr.next) ? null : twoStepsPtr.next.next; } midPtr.next = null; ListNode dummyHead = new ListNode(0), node = null; while (oneStepPtr != null) { node = oneStepPtr; oneStepPtr = oneStepPtr.next; node.next = dummyHead.next; dummyHead.next = node; } ListNode ptr = head; dummyHead = dummyHead.next; while (ptr != null && dummyHead != null) { node = ptr; ptr = ptr.next; ListNode qNode = dummyHead; dummyHead = dummyHead.next; qNode.next = ptr; node.next = qNode; } }}