LeetCode 2: Add Two Numbers (Linked List Simulation)
LeetCode 2Linked ListSimulationCarryToday we solve LeetCode 2 - Add Two Numbers.
Source: https://leetcode.com/problems/add-two-numbers/
English
Problem Summary
Two non-empty linked lists represent two non-negative integers in reverse digit order. Each node stores one digit. Add the two numbers and return the sum as a linked list, also in reverse order.
Key Insight
This is exactly elementary addition: add current digits and carry, output sum % 10, and move carry to sum / 10. Keep going while either list has nodes, and append a final node if carry remains.
Brute Force and Limitations
A brute-force idea is converting both linked lists into full integers, adding them, then converting back. This can overflow fixed-width types and is unnecessary. Digit-by-digit simulation is safer and cleaner.
Optimal Algorithm Steps
1) Create a dummy head and a tail pointer.
2) Initialize carry = 0.
3) While l1 != null or l2 != null or carry != 0:
• Read digit values (0 when list is exhausted).
• Compute sum = x + y + carry.
• Append node sum % 10 to result.
• Update carry = sum / 10.
4) Return dummy.next.
Complexity Analysis
Time: O(max(m, n)).
Space: O(max(m, n)) for the output list (excluding output, auxiliary space is O(1)).
Common Pitfalls
- Forgetting the final carry node (e.g., 9 + 1).
- Not handling different list lengths.
- Moving pointers before reading current values.
- Returning dummy head instead of dummy.next.
Reference Implementations (Java / Go / C++ / Python / JavaScript)
/**
* 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 tail = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int x = (l1 != null) ? l1.val : 0;
int y = (l2 != null) ? l2.val : 0;
int sum = x + y + carry;
tail.next = new ListNode(sum % 10);
tail = tail.next;
carry = sum / 10;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummy.next;
}
}/**
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
carry := 0
for l1 != nil || l2 != nil || carry != 0 {
x, y := 0, 0
if l1 != nil {
x = l1.Val
l1 = l1.Next
}
if l2 != nil {
y = l2.Val
l2 = l2.Next
}
sum := x + y + carry
tail.Next = &ListNode{Val: sum % 10}
tail = tail.Next
carry = sum / 10
}
return dummy.Next
}/**
* 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
int x = l1 ? l1->val : 0;
int y = l2 ? l2->val : 0;
int sum = x + y + carry;
tail->next = new ListNode(sum % 10);
tail = tail->next;
carry = sum / 10;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
return dummy.next;
}
};# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1, l2):
dummy = ListNode(0)
tail = dummy
carry = 0
while l1 or l2 or carry:
x = l1.val if l1 else 0
y = l2.val if l2 else 0
total = x + y + carry
tail.next = ListNode(total % 10)
tail = tail.next
carry = total // 10
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next/**
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
var addTwoNumbers = function(l1, l2) {
const dummy = new ListNode(0);
let tail = dummy;
let carry = 0;
while (l1 !== null || l2 !== null || carry !== 0) {
const x = l1 ? l1.val : 0;
const y = l2 ? l2.val : 0;
const sum = x + y + carry;
tail.next = new ListNode(sum % 10);
tail = tail.next;
carry = Math.floor(sum / 10);
l1 = l1 ? l1.next : null;
l2 = l2 ? l2.next : null;
}
return dummy.next;
};中文
题目概述
两个非空链表按逆序存储两个非负整数，每个节点存一位数字。要求返回它们相加后的结果链表，结果也按逆序存储。
核心思路
本质就是小学竖式加法：当前位相加再加进位，当前节点写 sum % 10，进位更新为 sum / 10。任一链表没走完都要继续，最后若还有进位要补节点。
暴力解法与不足
暴力法可先把链表转整数再相加再转回链表，但会遇到大数溢出风险，也违背链表逐位处理的题目意图。逐位模拟更稳妥。
最优算法步骤
1）建一个哑节点 dummy 和尾指针 tail。
2）初始化 carry = 0。
3）当 l1 != null 或 l2 != null 或 carry != 0 时循环：
• 读取当前位（链表为空按 0 处理）。
• 计算 sum = x + y + carry。
• 追加新节点值 sum % 10。
• 更新进位 carry = sum / 10。
4）返回 dummy.next。
复杂度分析
时间复杂度：O(max(m, n))。
空间复杂度：输出链表占 O(max(m, n))（不计输出时辅助空间为 O(1)）。
常见陷阱
- 忘记处理最后一位进位（如 9 + 1）。
- 两条链表长度不同未处理好。
- 读值前就移动指针导致丢位。
- 返回了 dummy 而不是 dummy.next。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
/**
* 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 tail = dummy;
int carry = 0;
while (l1 != null || l2 != null || carry != 0) {
int x = (l1 != null) ? l1.val : 0;
int y = (l2 != null) ? l2.val : 0;
int sum = x + y + carry;
tail.next = new ListNode(sum % 10);
tail = tail.next;
carry = sum / 10;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
return dummy.next;
}
}/**
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
tail := dummy
carry := 0
for l1 != nil || l2 != nil || carry != 0 {
x, y := 0, 0
if l1 != nil {
x = l1.Val
l1 = l1.Next
}
if l2 != nil {
y = l2.Val
l2 = l2.Next
}
sum := x + y + carry
tail.Next = &ListNode{Val: sum % 10}
tail = tail.Next
carry = sum / 10
}
return dummy.Next
}/**
* 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy(0);
ListNode* tail = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
int x = l1 ? l1->val : 0;
int y = l2 ? l2->val : 0;
int sum = x + y + carry;
tail->next = new ListNode(sum % 10);
tail = tail->next;
carry = sum / 10;
if (l1) l1 = l1->next;
if (l2) l2 = l2->next;
}
return dummy.next;
}
};# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1, l2):
dummy = ListNode(0)
tail = dummy
carry = 0
while l1 or l2 or carry:
x = l1.val if l1 else 0
y = l2.val if l2 else 0
total = x + y + carry
tail.next = ListNode(total % 10)
tail = tail.next
carry = total // 10
l1 = l1.next if l1 else None
l2 = l2.next if l2 else None
return dummy.next/**
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
var addTwoNumbers = function(l1, l2) {
const dummy = new ListNode(0);
let tail = dummy;
let carry = 0;
while (l1 !== null || l2 !== null || carry !== 0) {
const x = l1 ? l1.val : 0;
const y = l2 ? l2.val : 0;
const sum = x + y + carry;
tail.next = new ListNode(sum % 10);
tail = tail.next;
carry = Math.floor(sum / 10);
l1 = l1 ? l1.next : null;
l2 = l2 ? l2.next : null;
}
return dummy.next;
};
Comments