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}.
这道题分三步：
1：首先将原来的链表拆分成两部分，用next和next.next分
2：将第二部分链表反转
3：将第一部分链表和第二部分反转了的链表merge
Takeaway Messages from This Problem
The three steps can be used to solve other problems of linked list. A little diagram may help better understand them.
Reverse List:
Merge List:
下面附上程序源码：
public void reorderList(ListNode head) {if(head == null || head.next==null) { return; } ListNode walker = head; ListNode runner = head; while(runner.next!=null && runner.next.next!=null) { walker = walker.next; runner = runner.next.next; } ListNode head1 = head; ListNode head2 = walker.next; walker.next = null; head2 = reverse(head2); while(head1!=null && head2!=null) { ListNode next = head2.next; head2.next = head1.next; head1.next = head2; head1 = head2.next; head2 = next; } }private ListNode reverse(ListNode head) { ListNode pre = null; ListNode cur = head; while(cur!=null) { ListNode next = cur.next; cur.next = pre; pre = cur; cur = next; } return pre; }
