当前位置:首页 > 力扣 > 力扣面试题02.05链表相加:虚拟头节点+迭代解法的详细解析

力扣面试题02.05链表相加:虚拟头节点+迭代解法的详细解析

2天前

力扣面试题02.05链表相加:虚拟头节点+迭代解法的详细解析 力扣面试题 链表相加 虚拟头节点 进位处理 面试题 力扣题解 链表 迭代 第1张

一、题目解读

力扣面试题02.05要求将两个链表表示的整数相加,每个节点存储一位数字(逆序),结果同样以链表形式返回。例如,链表1为7→2→4,链表2为5→6→3,相加结果应为2→9→8→7。题目难点在于处理链表长度不一致、末尾进位以及逆序数字的相加逻辑。

二、解题思路

采用虚拟头节点+迭代的方法,核心思想是:

1. 创建虚拟头节点(dummy)避免处理头节点为空的边界条件;

2. 通过迭代同时遍历两个链表,逐位相加并处理进位;

3. 利用carry变量记录当前位进位,每次迭代更新节点值(sum % 10)与进位(sum / 10);

4. 当任一链表未遍历完或存在进位时,继续迭代,确保处理末尾进位(如5+7=12需额外节点)。

该解法简洁高效,无需额外数据结构时间复杂度O(max(m,n)),空间复杂度O(1)。

三、解题步骤

1. 初始化:创建虚拟头节点dummy,当前指针curr指向dummy,进位carry初始化为0;

2. 迭代相加:

    当l1或l2存在节点或carry>0时循环:

        计算当前位和sum(包含进位+节点值);

        更新进位carry = sum / 10;

        创建新节点存储sum % 10,并链接到curr->next;

        移动指针curr至新节点。

3. 处理末尾:循环结束后,若carry>0(如末尾进位),需额外添加节点;

4. 返回结果:虚拟头节点的下一个节点(即实际结果链表的头节点)。

四、代码与注释

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(0); // 虚拟头节点,简化边界处理
        ListNode* curr = &dummy; // 当前指针指向虚拟头节点
        int carry = 0; // 记录进位

        while (l1 || l2 || carry) { // 任一链表未遍历完或存在进位时继续
            int sum = carry; // 初始化当前位和
            if (l1) { // 若链表1有节点
                sum += l1->val; // 累加节点值
                l1 = l1->next; // 移动指针
            }
            if (l2) { // 若链表2有节点
                sum += l2->val;
                l2 = l2->next;
            }
            
            carry = sum / 10; // 更新进位
            curr->next = new ListNode(sum % 10); // 创建新节点存储余数
            curr = curr->next; // 指针后移
        }
        
        return dummy.next; // 返回结果链表的头节点
    }
};

五、总结

本题关键在于利用虚拟头节点消除头节点为空的特殊判断,结合迭代与进位处理实现链表的逐位相加。需注意循环条件需同时考虑链表遍历状态与进位,避免遗漏末尾进位的情况。此外,该解法无需反转链表或额外空间,是解决链表相加问题的经典思路。

原创内容 转载请注明出处

分享给朋友:

相关文章

【力扣2846题】图论+二进制提升:高效解决连通性问题(附C++代码)

【力扣2846题】图论+二进制提升:高效解决连通性问题(附C++代码)

一、题目解读力扣2846题要求解决一个基于图连通性的操作优化问题。给定一个无向图,包含边权重,以及一系列查询,每个查询询问两点间路径的最小操作次数。题目关键在于高效计算路径上权重分布的统计信息,并转化...

【牛客157题】:反转链表指定区间(虚拟头节点解法)

【牛客157题】:反转链表指定区间(虚拟头节点解法)

一、题目解读牛客第157题要求反转链表中第m到n个节点(包含m和n)的区间,并保持其他节点顺序不变。例如,给定链表1→2→3→4→5,m=2,n=4,应返回1→4→3→2→5。题目重点在于处理边界条件...

力扣面试16.18题解析:模式匹配问题的算法优化与实现(动态规划+字符串匹配)

力扣面试16.18题解析:模式匹配问题的算法优化与实现(动态规划+字符串匹配)

一、题目解读力扣面试16.18题要求判断字符串value是否可通过替换模式串pattern中的字符"a"和"b"(任意非空子串)进行匹配。例如,模式"...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。