题目链接：https://leetcode-cn.com/problems/reorder-list/
题解：
方法一：利用vector存放链表，使用双指针进行重排
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 public:
13 void reorderList(ListNode* head) {
14 if (head == nullptr) {
15 return;
16 }
17 vector <ListNode*> res;
18 ListNode * node = head;
19 while (node != nullptr) {
20 res.push_back(node);
21 node = node->next;
22 }
23 int i = 0, j = res.size() - 1;
24 while (i < j) {
25 res[i]->next = res[j];
26 i++;
27 if (i == j)
28 break;
29 res[j]->next = res[i];
30 j--;
31 }
32 res[i]->next = nullptr;
33 }
34 };
方法二：使用双向队列(还没学，待补)
方法三：将链表从中间分为俩部分，然后将后半部分逆转，最后将俩部分进行合并
/** 查找中间指针的方法，使用俩个指针，快指针每次移动俩个位置，慢指针每次移动一个位置，当快指针到达尾部时，慢指针正好到达了中间位置
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 public:
13 void reorderList(ListNode* head) {
14 ListNode * leftList = head;//左半部分
15 ListNode * rightList = getMidNode(head);//右半部分
16 ListNode * leftlast = rightList;//左半部分末尾节点
17 rightList = reverseList(rightList);//右半部分逆序操作
18 //依次左半部分、右半部分取节点
19 ListNode * left = leftList;
20 ListNode * right = rightList;
21 ListNode * temp = new ListNode(0);
22 while( left != leftlast || right != nullptr )
23 {
24 if( left != leftlast )
25 {
26 temp->next = left;
27 temp = temp->next;
28 left = left->next;
29 }
30 if( right != nullptr )
31 {
32 temp->next = right;
33 temp = temp->next;
34 right = right->next;
35 }
36 }
37 head = temp->next;
38 }
39 //双指针获取链表中间节点
40 ListNode* getMidNode(ListNode* head)
41 {
42 ListNode * fast = head;
43 ListNode * slow = head;
44 while(fast && fast->next)
45 {
46 fast = fast->next;
47 fast = fast->next;//快指针一次走两步
48 slow = slow->next;//慢指针一次走一步
49 }
50 return slow;
51 }
52 //链表的逆序操作
53 ListNode * reverseList(ListNode* head)
54 {
55 ListNode * prenode = nullptr;//前个节点
56 ListNode * node = head;//当前节点
57 ListNode * nextnode = head;//下个节点
58 while( node )
59 {
60 nextnode = node->next;//保存下个节点
61 node->next = prenode; //当前节点连到上个节点
62 prenode = node;//更新上个节点
63 node = nextnode ;//更新当前节点
64 }
65 return prenode;
66 }
67 };
68
69
70 作者：li-zhi-chao-4
71 链接：https://leetcode-cn.com/problems/reorder-list/solution/lian-biao-de-zhong-jian-jie-dian-ni-xu-he-bing-by-/
72 来源：力扣(LeetCode)
73 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。