刷爆 LeetCode！链表高频经典题双解，双指针 + 模拟加法直接拿捏

链表作为数据结构的经典考点更是 LeetCode 面试中的常客其中合并两个有序链表和两数相加堪称入门必刷、面试必考的高频题。这两道题分别对应双指针遍历和模拟数学运算两大核心思路吃透这两道题能轻松打通链表解题的任督二脉今天就带大家手把手拆解这两道题从核心思路到代码实现一步到位讲清楚新手也能轻松看懂、直接上手写一、LeetCode21. 合并两个有序链表 | 双指针遍历丝滑合并题目核心要求将两个升序排列的单链表合并为一个新的升序单链表新链表通过拼接原有节点组成无需创建新节点。核心解题思路双指针同步遍历这道题的核心是利用双指针分别指向两个链表的当前节点通过比较节点值的大小选择更小的节点接入结果链表直到其中一个链表遍历完毕最后将未遍历完的链表直接拼接到结果链表末尾即可。关键技巧创建虚拟头节点哑节点避免单独处理结果链表头节点的边界问题让代码逻辑更统一。完整可提交代码java运行/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 虚拟头节点拴住结果链表避免头节点边界处理 ListNode dummyNode new ListNode(0); // 遍历指针负责拼接节点 ListNode cur dummyNode; // 双指针同步遍历两个链表直到其中一个遍历完毕 while (list1 ! null list2 ! null) { // 选择值更小的节点接入结果链表 if (list1.val list2.val) { cur.next list1; list1 list1.next; } else { cur.next list2; list2 list2.next; } // 遍历指针后移准备接下一个节点 cur cur.next; } // 拼接剩余未遍历完的链表最多一个有剩余 cur.next list1 null ? list2 : list1; // 虚拟头节点的下一个节点才是结果链表的真正头节点 return dummyNode.next; } }代码核心解析虚拟头节点dummyNode初始化一个值为 0 的空节点作为结果链表的 “哨兵”让后续节点拼接无需判断头节点是否为空简化逻辑遍历指针cur始终指向结果链表的最后一个节点负责完成节点的拼接操作双指针遍历list1和list2分别作为两个原链表的遍历指针每次比较后移动值更小的指针保证结果链表升序剩余链表拼接当一个链表遍历完时另一个链表的剩余节点本身就是升序的直接拼接到结果链表末尾即可无需再逐个比较。复杂度分析时间复杂度O(mn)m和n分别为两个链表的长度每个节点仅遍历一次空间复杂度O(1)仅使用常数个额外指针无额外空间开销。二、LeetCode2. 两数相加 | 模拟加法倒序求和超简单题目核心要求两个非空链表分别表示两个非负整数链表逆序存储数字的每一位个位在链表头将两数相加后以同样的链表形式返回结果。核心解题思路模拟手工加法运算这道题的本质是模拟我们日常手工做加法的过程从个位开始逐位相加计算当前位的结果和进位进位传递到下一位继续计算。核心要点用虚拟头节点拴住结果链表统一节点拼接逻辑循环条件需包含链表 1 未遍历完、链表 2 未遍历完、还有进位三种情况避免遗漏最后一位的进位若链表节点为 null视为该位值为 0保证加法逻辑统一。完整可提交代码java运行/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val val; } * ListNode(int val, ListNode next) { this.val val; this.next next; } * } */ class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // 虚拟头节点拴住结果链表 ListNode dummy new ListNode(0); // 遍历指针负责拼接新节点 ListNode cur dummy; int carry 0; // 进位标志初始为0 // 循环条件只要有链表没遍历完或还有进位就继续计算 while (l1 ! null || l2 ! null || carry ! 0) { // 节点为null时该位值取0 int val1 l1 null ? 0 : l1.val; int val2 l2 null ? 0 : l2.val; int sum val1 val2 carry; // 当前位的总和含上一位进位 carry sum / 10; // 计算新的进位总和除以10取整 cur.next new ListNode(sum % 10); // 当前位结果总和取余10 // 遍历指针后移 cur cur.next; // 原链表指针非空时后移 if (l1 ! null) l1 l1.next; if (l2 ! null) l2 l2.next; } // 返回结果链表的真正头节点 return dummy.next; } }代码核心解析进位变量carry记录每一位相加后的进位初始为 0每次计算后更新为sum/10最后一位相加若有进位会单独生成一个节点空节点处理通过三元运算符将 null 节点的位值置为 0避免空指针异常同时让长短链表的加法逻辑统一当前位计算sum%10得到当前位的实际结果比如sum15则当前位为 5进位为 1循环终止条件必须同时判断三个条件否则会出现最后一位进位丢失如 99911000或空指针问题。复杂度分析时间复杂度O(max(m,n))m和n分别为两个链表的长度循环次数为较长链表的长度 1最多空间复杂度O(1)仅使用常数个额外变量结果链表的节点为题目要求的输出不计入额外空间。三、两道题的通用解题技巧 链表解题心得这两道题虽然考点不同但都用到了链表解题的核心技巧掌握这些技巧能解决 80% 的链表基础题1. 虚拟头节点哑节点是万能神器几乎所有链表拼接、删除、翻转题都能用到核心作用是统一节点处理逻辑避免单独判断头节点的边界情况让代码更简洁、不易出错。2. 遍历指针必不可少定义一个专门的遍历指针负责节点操作拼接、删除、翻转避免修改原链表指针或虚拟头节点保证指针指向的准确性。3. 边界条件要考虑周全合并链表考虑其中一个链表为空的情况两数相加考虑链表长度不一致、最后一位有进位的情况所有链表题都要避免空指针异常判断节点是否为 null 后再操作。最后这两道题都是 LeetCode 链表题的入门经典也是面试中的高频送分题。合并两个有序链表的双指针思路还能延伸到合并 k 个有序链表、链表去重等题目两数相加的模拟运算思路可拓展到两数相加 II正序存储、二进制链表求和等题。