LeetCode: Reorder List

list的题最大的麻烦就在于细节，这题也是弄了挺久，思路很简单，双指针取终点，后面的list反向后搭一起就行了

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *reverse(ListNode *head) {
12         if (!head) return NULL;
13         ListNode *pre = NULL;
14         ListNode *next;
15         next = head->next;
16         while (head) {
17             head->next = pre;
18             pre = head;
19             head = next;
20             if (next) next = next->next;
21         }
22         return pre;
23     }
24     void reorderList(ListNode *head) {
25         ListNode *p, *q;
26         p = q = head;
27         if (!head) return;
28         while (q) {
29             q = q->next;
30             if (!q) break;
31             q = q->next;
32             if (!q) break;
33             p = p->next;
34         }
35         ListNode *ppre = p;
36         p = p->next;
37         ppre->next = NULL;
38         q = reverse(p);
39         p = head;
40         ListNode *pnext, *qnext;
41         while (p) {
42             pnext = p->next;
43             if (q) qnext = q->next;
44             else break;
45             p->next = q;
46             q->next = pnext;
47             p = pnext;
48             q = qnext;
49         }
50     }
51 };

第二次一次过，用function看起来更加清楚

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *reverse(ListNode *head) {
12         if (!head) return NULL;
13         ListNode *p = head;
14         ListNode *pre = NULL;
15         while (p) {
16             ListNode *pnext = p->next;
17             p->next = pre;
18             pre = p;
19             p = pnext;
20         }
21         return pre;
22     }
23     void merge(ListNode *p, ListNode *q) {
24         ListNode *head = p;
25         bool flag = true;
26         while (p && q) {
27             if (flag) {
28                 ListNode *pnext = p->next;
29                 p->next = q;
30                 p = pnext;
31                 flag = !flag;
32             }
33             else {
34                 ListNode *qnext = q->next;
35                 q->next = p;
36                 q = qnext;
37                 flag  =!flag;
38             }
39         }
40     }
41     void reorderList(ListNode *head) {
42         ListNode *p = head;
43         ListNode *q = head;
44         if (!head) return;
45         while (q && q->next) {
46             q = q->next->next;
47             if (!q) break;
48             p = p->next;
49         }
50         q = p->next;
51         p->next = NULL;
52         q = reverse(q);
53         p = head;
54         merge(p, q);
55     }
56 };

 1 /**
 2  * Definition for singly-linked list.
 3  * public class ListNode {
 4  *     public int val;
 5  *     public ListNode next;
 6  *     public ListNode(int x) { val = x; }
 7  * }
 8  */
 9 public class Solution {
10     public void ReorderList(ListNode head) {
11         ListNode p = head;
12         ListNode q = head;
13         if (head == null) return;
14         while (q != null && q.next != null) {
15             q = q.next.next;
16             if (q == null) break;
17             p = p.next;
18         }
19         q = p.next;
20         p.next = null;
21         q = reverse(q);
22         p = head;
23         merge(p, q);
24     }
25     void merge(ListNode p, ListNode q) {
26         ListNode head = p;
27         bool flag = true;
28         while (p != null && q != null) {
29             if (flag) {
30                 ListNode pnext = p.next;
31                 p.next = q;
32                 p = pnext;
33                 flag = !flag;
34             }
35             else {
36                 ListNode qnext = q.next;
37                 q.next = p;
38                 q = qnext;
39                 flag = !flag;
40             }
41         }
42     }
43     public ListNode reverse(ListNode head) {
44         if (head == null) return null;
45         ListNode p = head;
46         ListNode pre = null;
47         while (p != null) {
48             ListNode pnext = p.next;
49             p.next = pre;
50             pre = p;
51             p = pnext;
52         }
53         return pre;
54     }
55 }

View Code