[leetcode]143. 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.

思路：

1. find mid

2. cut list

3. reverse slow part

4. merge two parts

代码：

 1 class Solution {
 2     public void reorderList(ListNode head) {
 3         // corner case
 4         if(head == null || head.next == null) return;
 5         // init 
 6         ListNode fast = head;
 7         ListNode slow = head;
 8         ListNode prev = null; 
 9         // find mid
10         while(fast != null && fast.next != null){
11             prev = slow;
12             slow = slow.next;
13             fast = fast.next.next;
14         }
15         //cut list
16         prev.next = null;
17         //recurse  slow part
18         slow = reverse(slow);
19         fast = head;
20         // merge two parts
21         while(fast.next!=null){
22             ListNode temp = fast.next; 
23             fast.next = slow; 
24             slow = slow.next;
25             fast.next.next = temp;
26             fast = temp;
27         } 
28         fast.next = slow; 
29     }
30     
31     private ListNode reverse(ListNode head){
32         ListNode cur = head;
33         ListNode pre = null;
34         while(cur != null){
35             ListNode temp = cur.next;
36             cur.next = pre; 
37             pre=cur;
38             cur=temp;
39         }
40         return pre; 
41     }
42 }