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

LeetCode Hot 100 | 链表上· 基础操作C 题解链表是面试高频考点。本文涵盖 LeetCode Hot 100 中 4 道链表基础题涉及双指针、快慢指针、原地反转等核心链表操作技巧。目录LeetCode Hot 100 | 链表上· 基础操作C 题解一、160. Intersection of Two Linked Lists相交链表 简单题目描述解题思路C 代码二、206. Reverse Linked List反转链表 简单题目描述解题思路C 代码三、234. Palindrome Linked List回文链表 简单题目描述解题思路C 代码四、141. Linked List Cycle环形链表 简单题目描述解题思路C 代码总结一、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中节点数目为mlistB中节点数目为n1 m, n 3 * 10^40 skipA m0 skipB n如果listA和listB没有交点intersectVal为0解题思路暴力思路对 A 中每个节点遍历 B 查找是否存在相同节点地址相同。O(mn) 时间O(1) 空间超时。哈希表思路遍历 A 把所有节点存入哈希集合再遍历 B 看是否命中。O(mn) 时间O(m) 空间可以但空间不优。双指针等长法本解两个指针tmpA和tmpB分别从headA和headB出发同步前进。当某个指针走到链表末尾nullptr时将其重定向到另一条链表的头部继续走。为什么这样能找到交点设 A 的非公共段长为aB 的非公共段长为b公共段长为c。tmpA走过路径a c b走完 A 后从 headB 出发走 b 步到交点tmpB走过路径b c a走完 B 后从 headA 出发走 a 步到交点两者走的总步数相等都是a b c因此同时到达交点。若无交点两者同时走到nullptr循环结束返回nullptr。举例走一遍示例 1A4 → 1 → [8 → 4 → 5] B5 → 6 → 1 → [8 → 4 → 5] 公共段8 → 4 → 5c3a2b3tmpA路径4,1,8,4,5,null → headB → 5,6,1,[8] ← 在这里相遇tmpB路径5,6,1,8,4,5,null → headA → 4,1,[8] ← 在这里相遇两者均在走了2338步后到达节点 8✅若无交叉示例 2两者各走mn步后同时为nullptrtmpA tmpB退出循环返回nullptr✅复杂度时间 O(mn)空间 O(1)C 代码/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */classSolution{public:ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){ListNode*tmpAheadA;ListNode*tmpBheadB;while(tmpA!tmpB){tmpAtmpA?tmpA-next:headB;tmpBtmpB?tmpB-next:headA;}returntmpA;}};二、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解题思路递归思路递归到链表末尾回溯时逐步反转指针。代码简洁但递归栈深度 O(n)空间不优。迭代原地反转本解三指针滚动前进prev已反转部分的头、cur当前处理节点、tmp暂存下一节点。每次迭代tmp cur-next保存下一节点防止断链cur-next prev当前节点的 next 反转指向已反转部分prev cur已反转部分前移一位cur tmp处理下一节点循环结束时cur nullptrprev就是新的头节点。举例走一遍[1,2,3,4,5]初始prevnull, cur1→2→3→4→5 迭代1tmp2, 1→null, prev1, cur2 迭代2tmp3, 2→1→null, prev2, cur3 迭代3tmp4, 3→2→1→null, prev3, cur4 迭代4tmp5, 4→3→2→1→null, prev4, cur5 迭代5tmpnull, 5→4→3→2→1→null, prev5, curnull 返回 prev5 ✅复杂度时间 O(n)空间 O(1)C 代码classSolution{public:ListNode*reverseList(ListNode*head){ListNode*curhead;ListNode*prevnullptr;while(cur){ListNode*tmpcur-next;cur-nextprev;prevcur;curtmp;}returnprev;}};三、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解题思路暴力思路遍历链表把所有值存入数组再用双指针判断数组是否回文。O(n) 时间O(n) 空间。O(1) 空间快慢指针 原地反转后半段本解三步走找中点快指针每次走 2 步慢指针每次走 1 步快指针到尾时慢指针恰好在链表中点反转后半段从中点开始原地反转后半段链表复用 206 题的反转逻辑逐一比对用两个指针分别从头和反转后的尾部向中间推进逐节点比较值找中点的边界细节链表长度为奇数如1→2→3→2→1慢指针停在中间节点 3Reverse(3)得到3→2→1从头比较1,2vs 从尾比较1,2中间的 3 不参与比较✅链表长度为偶数如1→2→2→1快指针走两步1→3→null慢指针走两步停在第二个 2Reverse(second_2)得到2→1从头比较1,2vs 从尾比较1,2✅举例走一遍[1,2,2,1]① 找中点 fast: 1→3→null, slow: 1→2→[2]停在第二个2 ② 反转后半段 middle 第二个2节点 Reverse(middle): null←2←1 → 返回1节点, head21→2→null ③ 比对 head1, head21 → 相等 head2, head22 → 相等 head2null → 循环结束返回true ✅举例走一遍[1,2]① 找中点fast1, fast-next2, fast-next-nextnull → 循环不进入 slow停在1, 但fast-next2满足条件后走一步, slow2 更仔细初始fastslow1 - fast(1)且fast-next(2) → fastnull, slow2 循环结束, middle2 ② 反转后半段: head22→null ③ 比对: head1, head22 → 不相等返回false ✅复杂度时间 O(n)空间 O(1)C 代码classSolution{public:ListNode*Middle(ListNode*head){ListNode*fasthead;ListNode*slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;}returnslow;}ListNode*Reverse(ListNode*head){ListNode*curhead;ListNode*prevnullptr;while(cur){ListNode*tmpcur-next;cur-nextprev;prevcur;curtmp;}returnprev;}boolisPalindrome(ListNode*head){ListNode*middleMiddle(head);ListNode*head2Reverse(middle);while(head2){if(head2-val!head-val)returnfalse;head2head2-next;headhead-next;}returntrue;}};四、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^5pos为-1或者链表中的一个有效索引解题思路哈希表思路遍历链表把每个节点地址存入哈希集合若发现已存在说明有环。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 初始fast3, slow3 迭代1fast0(走2步: 3→2→0), slow2(走1步: 3→2) 迭代2fast2(走2步: 0→-4→2), slow0(走1步: 2→0) 迭代3fast0(走2步: 2→0→-4 不对2→00→-4), slow-4 fast-4→2... 实际fast走2→0→-4, slow走0→-4 迭代3修正fast2→0-4的next2... 更简洁fast和slow最终都在环内循环每轮fast比slow快1步必然相遇 ✅无环情况示例 3[1]初始fast1, slow1 while: fast(1)且fast-next(null) → 条件不满足直接退出 返回 false ✅复杂度时间 O(n)空间 O(1)C 代码classSolution{public:boolhasCycle(ListNode*head){ListNode*fasthead;ListNode*slowhead;while(fastfast-next){fastfast-next-next;slowslow-next;if(fastslow)returntrue;}returnfalse;}};总结题号题目难度核心技巧时间复杂度空间复杂度160相交链表 简单双指针互换链表头O(mn)O(1)206反转链表 简单三指针迭代原地反转O(n)O(1)234回文链表 简单快慢指针找中点 反转后半段O(n)O(1)141环形链表 简单快慢指针 Floyd 判环O(n)O(1)链表双指针的三种经典模型同步等长两指针走相同步数利用路径总长相等消除差异160快慢指针找中点快 2 慢 1快指针到尾时慢指针在中间234快慢指针判环快 2 慢 1有环必然相遇141Floyd 判环如果这篇文章对你有帮助欢迎点赞收藏 ⭐也欢迎在评论区交流