leetcode143 重排链表

思路：
记录一种递归的方法。
实现：
 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* work(ListNode* head, int len)
15     {
16         if (len == 1) return head;
17         if (len == 2) return head->next;
18         ListNode* tail = work(head->next, len - 2);
19         ListNode* hn = head->next;
20         ListNode* tmp = tail->next->next; 
21         head->next = tail->next;
22         tail->next->next = hn;
23         tail->next = tmp;
24         return tail;
25     }
26     void reorderList(ListNode* head)
27     {
28         if (!head) return;
29         int len = 0;
30         ListNode* tmp = head;
31         while (tmp) { len++; tmp = tmp->next; }
32         work(head, len);
33     }
34 };