day136—快慢指针—重排链表（LeetCode-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→5→2→4→3，1→2→3→4 变为 1→4→2→3），通过「找中点 + 反转后半段 + 交替拼接」三步实现，时间复杂度O(n)、空间复杂度O(1)，是该问题的最优解法。

核心逻辑

代码整合了 “找链表中点”“反转链表” 两个基础操作，再通过双指针交替拼接完成重排，全程无额外空间开销：

1. 第一步：找链表中点：调用midNode函数（快慢指针法）找到链表中间节点mid，将原链表拆分为前半段（head开头）和后半段（mid开头）；
2. 第二步：反转后半段：调用reverseNode函数反转后半段链表，得到反转后的后半段头节点head2；
3. 第三步：交替拼接：用两个指针分别遍历前半段和反转后的后半段，逐个将后半段节点插入前半段节点之间，直到后半段只剩最后一个节点（避免链表成环），完成重排。

总结

1. 核心思路：将重排问题拆解为 “找中点拆分 + 反转后半段 + 交替拼接” 三个基础链表操作，化繁为简；
2. 关键细节：拼接时循环条件为head2->next（而非head2），避免最后拼接导致链表闭环；
3. 效率优势：三步操作均为一次遍历，整体时间O(n)、空间O(1)，是重排链表的最优解法。

函数源码：

/** * 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: //找中间结点——快慢指针 ListNode* midNode(ListNode* head){ ListNode* slow=head; ListNode* fast=head; while(fast && fast->next){ slow=slow->next; fast=fast->next->next; } return slow; } //反转链表 ListNode* reverseNode(ListNode* head){ ListNode* pre=nullptr; ListNode* cur=head; ListNode* nxt=nullptr; while(cur){ nxt=cur->next; cur->next=pre; pre=cur; cur=nxt; } return pre; } void reorderList(ListNode* head) { ListNode* mid =midNode(head); ListNode* head2=reverseNode(mid); ListNode* nxt=nullptr; ListNode* nxt2=nullptr; while(head2->next){ nxt=head->next; nxt2=head2->next; head->next=head2; head2->next=nxt; head=nxt; head2=nxt2; } } };