leetcode143 重排链表

思路：
先找到链表中点，再反转后半部分，再merge两个子链表。
实现：
 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode() : val(0), next(nullptr) {}
 7  *     ListNode(int x) : val(x), next(nullptr) {}
 8  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 9  * };
10  */
11 class Solution
12 {
13 public:
14     ListNode* middleNode(ListNode* head)
15     {
16         if (head == NULL) return NULL;
17         ListNode* fast = head, *slow = head;
18         while (fast and fast->next)
19         {
20             fast = fast->next->next;
21             slow = slow->next;
22         }
23         return slow;
24     }
25     ListNode* reverse(ListNode* head)
26     {
27         if (head == NULL or head->next == NULL) return head;
28         ListNode* pre = head, *cur = head->next;
29         while (cur)
30         {
31             ListNode* nxt = cur->next;
32             cur->next = pre;
33             pre = cur;
34             cur = nxt;
35         }
36         head->next = NULL;
37         return pre;
38     }
39     void merge(ListNode* a, ListNode* b)
40     {
41         if (b == NULL) return;
42         while (a)
43         {
44             ListNode* x = a->next;
45             a->next = b;
46             ListNode* y = b->next;
47             if (x) b->next = x;
48             a = x;
49             b = y;
50         }
51     }
52     void reorderList(ListNode* head)
53     {
54         if (head == NULL or head->next == NULL) return;
55         ListNode* mid = middleNode(head);
56         ListNode* tmp = head;
57         while (tmp->next != mid) tmp = tmp->next;
58         tmp->next = NULL;
59         auto l = reverse(mid);
60         merge(head, l);
61     }
62 };