Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You must do this in-place without altering the nodes' values.
For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.
分为3步，先求出中间节点，再原地反转链表，最后链表合并。
要注意2点：
（1）最好不要把反转链表抽取出来作为一个函数，会TLE
（2）反转链表时要从中间切开来
/* * 应该就是调用函数花销大的缘故 */ public class Solution { public void reorderList(ListNode head) { if(head == null)return; // 快慢指针求出中间节点 ListNode slow = head, fast = head; while(fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; } ListNode middle = slow; // in place 反转链表 ListNode pre = slow, cur = slow.next, next; slow.next = null; // 从中间断开 while(cur != null) { next = cur.next; cur.next = pre; pre = cur; cur = next; } // 链表合并 ListNode head2 = pre; ListNode tmp1, tmp2; while(head2 != middle) { tmp1 = head.next; tmp2 = head2.next; head2.next = head.next; head.next = head2; head = tmp1; head2 = tmp2; } } }
