【链表】重排链表，看似复杂实则并不简单~

143. 重排链表

143. 重排链表

​ 给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

​ 请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

​ 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1：

输入：head = [1,2,3,4]
输出：[1,4,2,3]

示例 2：

输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]

提示：

• 链表的长度范围为 [1, 5 * 104]
• 1 <= node.val <= 1000

---

解题思路

​ 这道题如果我们直接重排的话，那么时间复杂度比较高，并且程序也比较复杂，所以我们要分解问题来分析！

​ 仔细想想，这道题无非就是让链表从头和从末尾开始每一个节点进行合并，那不就相当于是两个链表的合并操作吗对不对！并且其中一个链表就是原链表中的前半部分，另一个链表是原链表中后半部分的逆序，比如例子中的 1->2->3->4->5，前半部分可以看作是 1->2->3（这道题也可以看作是 1->2，最后合并结果都是一样的），后半部分则是逆序的情况：5->4，此时将它们逐个合并起来就是 1->5->2->4->3 了！

​ 根据上面的解析，我们可以把这道题分为三步来解决：

1. 找到链表的中间节点（使用快慢指针就能得到，此时 slow 就是中间节点）
2. 逆序中间节点的右侧链表（可以使用双指针或者头插法，下面再讨论）
3. 合并左右两个链表

​ 上面的操作我们都是耳熟能详啦，其中要注意的无非就是第二步，这里介绍 头插法的使用，其实就是引入一个新的头节点 newhead，将右侧链表中的节点逐个头插到 newhead 后面，最后得到一个只有后半部分的逆序链表，而原链表中就剩下前半部分！只不过要注意一些细节，下面我们来讨论一下！（至于双指针的做法，这里就不介绍了，其实相对头插法来说没那么好理解！）

​ 因为链表的个数可以为奇数或者是偶数，所以我们要考虑一下中间节点 slow 是否要包括在头插法和逆序的操作中，所以此时我们使用头插法的时候有两种策略：

1. 将中间节点 slow 后面的链表进行逆序，包括中间节点 slow：

   • 其实这种情况下无论是链表个数是奇数还是偶数的话，使用头插法的时候都不太好整，因为可能会出现一些 bug，如下图所示：

     

   • 因为我们最后是要将后半部分单独拎出来作为一个逆序链表，但是此时有一个问题，就是 slow 前面的节点的 next 是指向 slow 的，因为我们要断开左右部分的链接，此时需要将其 slow 前面的节点的 next 置为空，不然在后面合并遍历的时候，就会死循环。但问题是这是一个单链表，要找到前面的节点的话势必要重新遍历，时间复杂度就提高了，所以这种包括中间节点的也一起头插和逆序的操作是 不推荐 的，不如使用下面的策略！

2. 将中间节点 slow 后面的链表进行逆序，但 不包括中间节点 slow：

   • 此时这种情况就比较好办了，无论链表的个数是奇数还是偶数，此时中间节点最后都不属于右半部分的，而是属于前半部分的，那么同样两个链表要断开连接的话，就在中间节点 slow 断开，这就非常简单了，直接就是一个 slow->next = nullptr 就解决了，非常的高效和简单！

     

   • 比如举个例子，如下图所示：

     

​ 此外需要注意的细节就是，在进行逆序头插法的时候，需要先记录一下当前节点的下一个节点，防止指向改变后丢失，其它就没有什么大问题了！

​ 解决了第二步，那么第三步就没问题了，就是要将右侧链表的每个节点插入到左侧链表的每个节点中！下面直接给出代码，具体过程可以结合自己画图来分析，都是不难的，只是流程多而已

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:void reorderList(ListNode* head) {// 1. 找到链表的中间节点ListNode* fast = head;ListNode* slow = head;while(fast != nullptr && fast->next != nullptr){slow = slow->next;fast = fast->next->next;}// 2. 逆序中间节点之后的链表，但不包括中间节点（此时slow就是中间节点）ListNode* newhead = new ListNode(0, nullptr);ListNode* right = slow->next;while(right != nullptr){ListNode* next = right->next; // 先记录下一个节点防止丢失right->next = newhead->next;newhead->next = right;right = next;}// 3. 合并左右两个链表slow->next = nullptr; // 记得要断开左右链表的连接，不然会死循环ListNode* cur1 = head;ListNode* cur2 = newhead->next;while(cur1 != nullptr && cur2 != nullptr){ListNode* next1 = cur1->next;ListNode* next2 = cur2->next;cur1->next = cur2;cur2->next = next1;cur1 = next1;cur2 = next2;}delete newhead; // 别忘了要释放节点}
};