LeetCode Hot 100 | 链表（上）· 基础操作（C++ 题解）

jcm0903

408人浏览 · 2026-04-02 09:11:23

jcm0903 · 2026-04-02 09:11:23 发布

LeetCode Hot 100 | 链表（上）· 基础操作（C++ 题解）

Hot100 链表（上）：160 / 206 / 234 / 141。

一、160. Intersection of Two Linked Lists（相交链表）🟢 简单

题目描述

给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。

题目数据保证整个链式结构中不存在环。注意，函数返回结果后，链表必须保持其原始结构。

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'
解释：相交节点的值为 8。链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]，在 A 中交叉节点前有 2 个节点，在 B 中有 3 个节点。

示例 2：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection

提示：

listA 中节点数目为 m，listB 中节点数目为 n
1 <= m, n <= 3 * 10^4
0 <= skipA <= m，0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0

图解

160图解

解题思路

暴力思路： 对 A 中每个节点，遍历 B 查找是否存在相同节点（地址相同）。O(mn) 时间，O(1) 空间，超时。

哈希表思路： 遍历 A 把所有节点存入哈希集合，再遍历 B 看是否命中。O(m+n) 时间，O(m) 空间，可以但空间不优。

双指针等长法（本解）：

两个指针 tmpA 和 tmpB 分别从 headA 和 headB 出发同步前进。当某个指针走到链表末尾（nullptr）时，将其重定向到另一条链表的头部继续走。

为什么这样能找到交点？

设 A 的非公共段长为 a，B 的非公共段长为 b，公共段长为 c。

tmpA 走过路径：a + c + b（走完 A 后从 headB 出发走 b 步到交点）
tmpB 走过路径：b + c + a（走完 B 后从 headA 出发走 a 步到交点）

两者走的总步数相等（都是 a + b + c），因此同时到达交点。若无交点，两者同时走到 nullptr，循环结束返回 nullptr。

举例走一遍（示例 1）：

A：4 → 1 → [8 → 4 → 5]
B：5 → 6 → 1 → [8 → 4 → 5]
公共段：8 → 4 → 5（c=3），a=2，b=3

tmpA 路径：4,1,8,4,5,null → headB → 5,6,1,[8] ← 在这里相遇
tmpB 路径：5,6,1,8,4,5,null → headA → 4,1,[8] ← 在这里相遇

两者均在走了 2+3+3=8 步后到达节点 8，✅

若无交叉（示例 2）：两者各走 m+n 步后同时为 nullptr，tmpA == tmpB 退出循环，返回 nullptr ✅

复杂度： 时间 O(m+n)，空间 O(1)

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *tmpA = headA, *tmpB = headB;
        
        while(tmpA != tmpB) {
            tmpA = tmpA ? tmpA->next : headB;
            tmpB = tmpB ? tmpB->next : headA;
        }
        
        return tmpA;
    }
};

二、206. Reverse Linked List（反转链表）🟢 简单

题目描述

给你单链表的头节点 head，请你反转链表，并返回反转后的链表。

示例 1：

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

示例 2：

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

示例 3：

输入：head = []
输出：[]

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

图解

206图解

解题思路

递归思路： 递归到链表末尾，回溯时逐步反转指针。代码简洁，但递归栈深度 O(n)，空间不优。

迭代原地反转（本解）：

三指针滚动前进：prev（已反转部分的头）、cur（当前处理节点）、tmp（暂存下一节点）。

每次迭代：

tmp = cur->next（保存下一节点，防止断链）
cur->next = prev（当前节点的 next 反转，指向已反转部分）
prev = cur（已反转部分前移一位）
cur = tmp（处理下一节点）

循环结束时 cur == nullptr，prev 就是新的头节点。

举例走一遍（[1,2,3,4,5]）：

初始：prev=null, cur=1→2→3→4→5

迭代1：tmp=2, 1→null, prev=1, cur=2
迭代2：tmp=3, 2→1→null, prev=2, cur=3
迭代3：tmp=4, 3→2→1→null, prev=3, cur=4
迭代4：tmp=5, 4→3→2→1→null, prev=4, cur=5
迭代5：tmp=null, 5→4→3→2→1→null, prev=5, cur=null

返回 prev=5 ✅

复杂度： 时间 O(n)，空间 O(1)

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:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur = head;
        ListNode *prev = nullptr;
        
        while (cur) {
            ListNode *tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }
        
        return prev;
    }
};

三、234. Palindrome Linked List（回文链表）🟢 简单

题目描述

给你一个单链表的头节点 head，请你判断该链表是否为回文链表。如果是，返回 true；否则，返回 false。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围 [1, 10^5] 内
0 <= Node.val <= 9

图解

234图解

解题思路

暴力思路： 遍历链表把所有值存入数组，再用双指针判断数组是否回文。O(n) 时间，O(n) 空间。

O(1) 空间：快慢指针 + 原地反转后半段（本解）：

三步走：

找中点：快指针每次走 2 步，慢指针每次走 1 步，快指针到尾时慢指针恰好在链表中点
反转后半段：从中点开始，原地反转后半段链表（复用 206 题的反转逻辑）
逐一比对：用两个指针分别从头和反转后的尾部向中间推进，逐节点比较值

找中点的边界细节：

链表长度为奇数（如 1→2→3→2→1）：慢指针停在中间节点 3，Reverse(3) 得到 3→2→1，从头比较 1,2 vs 从尾比较 1,2，中间的 3 不参与比较，✅
链表长度为偶数（如 1→2→2→1）：快指针走两步（1→3→null），慢指针走两步停在第二个 2，Reverse(second_2) 得到 2→1，从头比较 1,2 vs 从尾比较 1,2，✅

举例走一遍（[1,2,2,1]）：

① 找中点：
   fast: 1→3→null, slow: 1→2→[2]（停在第二个2）

② 反转后半段：
   middle = 第二个2节点
   Reverse(middle): null←2←1 → 返回1节点, head2=1→2→null

③ 比对：
   head=1, head2=1 → 相等
   head=2, head2=2 → 相等
   head2=null → 循环结束，返回true ✅

举例走一遍（[1,2]）：

① 找中点：fast=1, fast->next=2, fast->next->next=null → 循环不进入
   slow停在1, 但fast->next=2满足条件后走一步, slow=2

   更仔细：初始fast=slow=1
   - fast(1)且fast->next(2) → fast=null, slow=2
   循环结束, middle=2

② 反转后半段: head2=2→null

③ 比对: head=1, head2=2 → 不相等，返回false ✅

复杂度： 时间 O(n)，空间 O(1)

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:
    ListNode *Middle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }
        
        return slow;
    }
    
    ListNode *Reverse(ListNode *head) {
        ListNode *cur = head;
        ListNode *prev = nullptr;
        
        while (cur) {
            ListNode *tmp = cur->next;
            cur->next = prev;
            prev = cur;
            cur = tmp;
        }
        
        return prev;
    }
    
    bool isPalindrome(ListNode* head) {
        ListNode *middle = Middle(head);
        ListNode *head2 = Reverse(middle);
        
        while (head2) {
            if (head2->val != head->val)
                return false;
            head2 = head2->next;
            head = head->next;
        }
        
        return true;
    }
};

四、141. Linked List Cycle（环形链表）🟢 简单

题目描述

给你一个链表的头节点 head，判断链表中是否有环。

如果链表中存在环，则返回 true。否则，返回 false。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 10^4]
-10^5 <= Node.val <= 10^5
pos 为 -1 或者链表中的一个有效索引

图解

141图解

解题思路

哈希表思路： 遍历链表，把每个节点地址存入哈希集合，若发现已存在说明有环。O(n) 时间，O(n) 空间。

快慢指针（Floyd 判环，本解）：

慢指针每次走 1 步，快指针每次走 2 步。

无环：快指针最终走到 nullptr，循环终止，返回 false
有环：快指针进入环后开始追赶慢指针。两者都在环内时，每轮迭代快指针追近 1 步，经过「环长」轮后必然相遇，返回 true

为什么一定会相遇（不会跳过）？

设慢指针进入环时，快指针在环内距慢指针 d 步。此后每次迭代，快指针多走 1 步，相对距离减少 1。当相对距离变为 0 时相遇。相对距离是整数递减，因此必然经过 0，不会跳过。

举例走一遍（示例 1，[3,2,0,-4]，尾部连接到索引1）：

链表结构：3 → 2 → 0 → -4
                ↑___________|（-4的next指向2）

初始：fast=3, slow=3

迭代1：fast=0(走2步: 3→2→0), slow=2(走1步: 3→2)
迭代2：fast=2(走2步: 0→-4→2), slow=0(走1步: 2→0)
迭代3：fast=0(走2步: 2→0→-4 不对，2→0，0→-4), slow=-4
       fast=-4→2=... 实际fast走：2→0→-4, slow走：0→-4
迭代3修正：fast=2→0=-4的next=2... 

更简洁：fast和slow最终都在环内循环，每轮fast比slow快1步，必然相遇 ✅

无环情况（示例 3，[1]）：

初始：fast=1, slow=1
while: fast(1)且fast->next(null) → 条件不满足，直接退出
返回 false ✅

复杂度： 时间 O(n)，空间 O(1)

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        
        while (fast && fast->next) {
            fast = fast->next->next;
            slow = slow->next;
            
            if (fast == slow)
                return true;
        }
        
        return false;
    }
};

总结

题号	题目	难度	核心技巧	时间复杂度	空间复杂度
160	相交链表	🟢 简单	双指针互换链表头	O(m+n)	O(1)
206	反转链表	🟢 简单	三指针迭代原地反转	O(n)	O(1)
234	回文链表	🟢 简单	快慢指针找中点 + 反转后半段	O(n)	O(1)
141	环形链表	🟢 简单	快慢指针 Floyd 判环	O(n)	O(1)