leetcode -- 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 must do this in-place without altering the nodes' values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

[解题思路]

将队列从中间断开，分成两个队列p1,p2，p2反转，然后将p1,p2进行合并

 1 public class Solution {
 2     public void reorderList(ListNode head) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5         if(head == null){
 6             return;
 7         }
 8         
 9         ListNode fast = head, slow = head;
10         while(fast.next != null && fast.next.next != null){
11             fast = fast.next.next;
12             slow = slow.next;
13         }
14         
15         ListNode p1 = head, p2 = slow.next;
16         // break from middle node
17         slow.next = null;
18         
19         p2 = reverseList(p2);
20         
21         mergeTwoList(head, p1, p2);
22     }
23     
24     public void mergeTwoList(ListNode head, ListNode p1, ListNode p2){
25         if(p2 == null){
26             return;
27         }
28         
29         head = new ListNode(-65536);
30         ListNode pResult = head;
31         int count = 0;
32         while(p1 != null && p2 != null){
33             if(count % 2 == 0){
34                 pResult.next = p1;
35                 pResult = pResult.next;
36                 p1 = p1.next;
37             } else {
38                 pResult.next = p2;
39                 pResult = pResult.next;
40                 p2 = p2.next;
41             }
42             count ++;
43         }
44         
45         while(p1 != null){
46             pResult.next = p1;
47             pResult = pResult.next;
48             p1 = p1.next;
49         }
50         while(p2 != null){
51             pResult.next = p2;
52             pResult = pResult.next;
53             p2 = p2.next;
54         }
55         head = head.next;
56     }
57     
58     public ListNode reverseList(ListNode head){
59         if(head == null || head.next == null){
60             return head;
61         }
62         ListNode cur = head.next, pre = head;
63         ListNode tmp = null;
64         pre.next = null;
65         
66         while(cur != null){
67             tmp = cur.next;
68             cur.next = pre;
69             pre = cur;
70             cur = tmp;
71         }
72         return pre;
73     }
74 }