LeetCode 第143题：重排链表

题目描述

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

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

请将其重新排列后变为：

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

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

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1：

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

示例 2：

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

提示

• 链表的长度范围为 [1, 5 * 10^4]
• 1 <= Node.val <= 1000

解题思路

方法一：线性表

最直观的解法是使用线性表存储该链表，然后利用线性表可以下标访问的特点，直接按顺序访问指定元素，重建该链表即可。

关键点：

1. 使用列表存储所有节点
2. 利用双指针从两端向中间遍历
3. 重新连接节点

具体步骤：

1. 遍历链表，将所有节点存入列表中
2. 使用左右指针分别指向列表的两端
3. 依次连接左右指针指向的节点
4. 最后一个节点的next指向null

时间复杂度：O(n)，其中 n 是链表的长度。
空间复杂度：O(n)，需要使用线性表存储链表中的节点。

方法二：寻找链表中点 + 链表逆序 + 合并链表

这种方法不需要额外的空间，但需要三个步骤：

1. 找到原链表的中点（使用快慢指针）
2. 将原链表的后半部分反转
3. 将前半部分和反转后的后半部分合并

关键点：

1. 使用快慢指针找到链表中点
2. 反转后半部分链表
3. 交替合并两个链表

具体步骤：

1. 使用快慢指针找到链表中点：
   • 慢指针每次走一步，快指针每次走两步
   • 当快指针到达末尾时，慢指针指向中点
2. 从中点处将链表断开，反转后半部分
3. 将前半部分与反转后的后半部分交替合并

时间复杂度：O(n)，其中 n 是链表的长度。
空间复杂度：O(1)，只需要常数的额外空间。

图解思路

方法一：线性表分析

以示例1为例：head = [1,2,3,4]

步骤	操作	链表状态	说明
初始状态	存储节点	[1,2,3,4]	将所有节点存入列表
第1步	连接1和4	1->4	left=0, right=3
第2步	连接2和3	1->4->2->3	left=1, right=2
第3步	设置结尾	1->4->2->3->null	最后节点指向null

方法二：三步法分析

以示例1为例：head = [1,2,3,4]

1. 找到中点：

步骤	慢指针	快指针	说明
初始状态	1	1	同时指向头节点
第1步	2	3	慢走一步，快走两步
第2步	3	null	快指针到达末尾，慢指针指向中点

2. 反转后半部分：

步骤	原链表	反转后	说明
初始状态	1->2 和 3->4	1->2 和 4->3	从中点断开，反转后半部分

3. 合并链表：

步骤	操作	结果	说明
第1步	连接1和4	1->4	取前半部分第一个和后半部分第一个
第2步	连接2和3	1->4->2->3	取前半部分第二个和后半部分第二个
最终	完成合并	1->4->2->3->null	设置结尾为null

代码实现

C# 实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public void ReorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }
        
        // 1. 找到中点
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 2. 反转后半部分
        ListNode mid = slow.next;
        slow.next = null;  // 断开前后两部分
        ListNode prev = null;
        while (mid != null) {
            ListNode temp = mid.next;
            mid.next = prev;
            prev = mid;
            mid = temp;
        }
        
        // 3. 合并两个链表
        ListNode first = head;
        ListNode second = prev;
        while (second != null) {
            ListNode temp1 = first.next;
            ListNode temp2 = second.next;
            
            first.next = second;
            second.next = temp1;
            
            first = temp1;
            second = temp2;
        }
    }
}

Python 实现

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head or not head.next:
            return
        
        # 1. 找到中点
        slow = fast = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        
        # 2. 反转后半部分
        mid = slow.next
        slow.next = None  # 断开前后两部分
        prev = None
        while mid:
            temp = mid.next
            mid.next = prev
            prev = mid
            mid = temp
        
        # 3. 合并两个链表
        first = head
        second = prev
        while second:
            temp1 = first.next
            temp2 = second.next
            
            first.next = second
            second.next = temp1
            
            first = temp1
            second = temp2

C++ 实现

/**
 * 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) {
        if (!head || !head->next) {
            return;
        }
        
        // 1. 找到中点
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // 2. 反转后半部分
        ListNode* mid = slow->next;
        slow->next = nullptr;  // 断开前后两部分
        ListNode* prev = nullptr;
        while (mid) {
            ListNode* temp = mid->next;
            mid->next = prev;
            prev = mid;
            mid = temp;
        }
        
        // 3. 合并两个链表
        ListNode* first = head;
        ListNode* second = prev;
        while (second) {
            ListNode* temp1 = first->next;
            ListNode* temp2 = second->next;
            
            first->next = second;
            second->next = temp1;
            
            first = temp1;
            second = temp2;
        }
    }
};

性能分析

各语言实现的性能对比：

实现语言	执行用时	内存消耗	特点
C#	92 ms	42.1 MB	实现简洁，性能适中
Python	84 ms	25.8 MB	代码最简洁，性能良好
C++	36 ms	17.4 MB	性能最优，内存占用最小

补充说明

代码亮点

1. 使用快慢指针找中点，避免了两次遍历
2. 原地反转链表，不需要额外空间
3. 合并时使用临时变量保存next节点，避免丢失引用

常见错误

1. 忘记处理空链表或单节点链表的特殊情况
2. 反转链表时没有正确处理节点的next指针
3. 合并时没有正确保存next节点导致链表断裂

相关题目

• 206. 反转链表
• 876. 链表的中间结点
  码亮点

1. 使用快慢指针找中点，避免了两次遍历
2. 原地反转链表，不需要额外空间
3. 合并时使用临时变量保存next节点，避免丢失引用

常见错误

1. 忘记处理空链表或单节点链表的特殊情况
2. 反转链表时没有正确处理节点的next指针
3. 合并时没有正确保存next节点导致链表断裂

相关题目

• 206. 反转链表
• 876. 链表的中间结点
• 234. 回文链表