- 作者简介：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名）
- ❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论，💬支持博主，记得点个大大的
关注，持续更新🤞
————————————————-
题目描述
给定两个非空链表来表示两个非负整数，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
解释：342 + 465 = 807
原题：LeetCode 2
思路及实现
方式一：模拟手工加法
思路
我们可以模拟手工加法的过程。从头开始遍历两个链表，将对应位置的数字相加，并处理进位。如果两个链表的长度不同，则较短的链表后面视为0。
代码实现
Java版本
public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // 哑节点，方便处理头节点 ListNode dummy = new ListNode(0); ListNode curr = dummy; int carry = 0; while (l1 != null || l2 != null) { int sum = carry; if (l1 != null) { sum += l1.val; l1 = l1.next; } if (l2 != null) { sum += l2.val; l2 = l2.next; } carry = sum / 10; curr.next = new ListNode(sum % 10); curr = curr.next; } // 如果最后还有进位，需要额外添加一个节点 if (carry > 0) { curr.next = new ListNode(carry); } return dummy.next; }
说明：
此代码使用了一个哑节点
dummy，它的next指向真正的头节点，方便我们处理链表的头节点。在遍历链表时，我们计算当前位置的和sum，包括进位carry。然后将和的个位数创建新的节点，curr指向新的节点继续遍历。最后，如果遍历完两个链表后还有进位，需要额外添加一个节点。
C语言版本
typedef struct ListNode { int val; struct ListNode *next; } ListNode; ListNode* createNode(int val) { ListNode* node = (ListNode*)malloc(sizeof(ListNode)); node->val = val; node->next = NULL; return node; } ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* dummy = createNode(0); ListNode* curr = dummy; int carry = 0; while (l1 != NULL || l2 != NULL) { int sum = carry; if (l1 != NULL) { sum += l1->val; l1 = l1->next; } if (l2 != NULL) { sum += l2->val; l2 = l2->next; } carry = sum / 10; curr->next = createNode(sum % 10); curr = curr->next; } if (carry > 0) { curr->next = createNode(carry); } return dummy->next; }
说明：
C语言版本与Java版本类似，不过需要注意C语言需要手动分配内存，并且使用
malloc来创建新的节点。
Python3版本
class ListNode: def __init__(self, x): self.val = x self.next = None def addTwoNumbers(l1: ListNode, l2: ListNode) -> ListNode: dummy = ListNode(0) curr = dummy carry = 0 while l1 or l2: sum_val = carry if l1: sum_val += l1.val l1 = ll1.next if l2: sum_val += l2.val l2 = l2.next carry = sum_val // 10 curr.next = ListNode(sum_val % 10) curr = curr.next if carry > 0: curr.next = ListNode(carry) return dummy.next
说明：
Python版本的代码结构与其他版本相似，但语法更简洁。在Python中，我们不需要显式地分配内存或管理指针，因为Python会自动处理这些。
Golang版本
package main import "fmt" type ListNode struct { Val int Next *ListNode } func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { dummy := &ListNode{} curr := dummy carry := 0 for l1 != nil || l2 != nil { sum := carry if l1 != nil { sum += l1.Val l1 = l1.Next } if l2 != nil { sum += l2.Val l2 = l2.Next } carry = sum / 10 curr.Next = &ListNode{Val: sum % 10} curr = curr.Next } if carry > 0 { curr.Next = &ListNode{Val: carry} } return dummy.Next } func main() { // 测试代码 // 创建链表 l1: 2 -> 4 -> 3 l1 := &ListNode{Val: 2} l1.Next = &ListNode{Val: 4} l1.Next.Next = &ListNode{Val: 3} // 创建链表 l2: 5 -> 6 -> 4 l2 := &ListNode{Val: 5} l2.Next = &ListNode{Val: 6} l2.Next.Next = &ListNode{Val: 4} // 调用函数 result := addTwoNumbers(l1, l2) // 打印结果 for result != nil { fmt.Print(result.Val, " ") result = result.Next } }
说明：
Golang版本同样使用了哑节点，代码结构和思路与其他版本一致。在Go中，我们使用指针来操作链表节点。
复杂度分析
- 时间复杂度：O(max(m, n))，其中m和n分别为两个链表的长度。我们需要遍历两个链表中的所有节点一次。
- 空间复杂度：O(max(m, n))。在最坏的情况下，当两个链表的长度不同时，结果链表的长度将等于较长链表的长度，因此需要额外分配相应数量的节点。
方式二：递归
思路
递归方式也可以解决这个问题。我们可以递归地调用addTwoNumbers函数来处理链表的剩余部分，并将结果和进位传递回上一层递归。
代码实现
Java版本
public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { return addTwoNumbersRecursive(l1, l2, 0); } private ListNode addTwoNumbersRecursive(ListNode l1, ListNode l2, int carry) { if (l1 == null && l2 == null && carry == 0) { return null; } int val1 = (l1 != null) ? l1.val : 0; int val2 = (l2 != null) ? l2.val : 0; int sum = val1 + val2 + carry; ListNode newNode = new ListNode(sum % 10); newNode.next = addTwoNumbersRecursive(l1 != null ? l1.next : null, l2 != null ? l2.next : null, sum / 10); return newNode; } }
说明：
如果其中一个链表为空，直接返回另一个链表。计算当前节点的和，并创建新的头节点。递归地处理链表剩余部分，并将结果连接到新头节点。如果当前和大于等于10，则处理进位。
C语言版本
#include <stdio.h> #include <stdlib.h> struct ListNode { int val; struct ListNode *next; }; struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { struct ListNode* head = NULL; struct ListNode** node = &head; int carry = 0; while (l1 || l2 || carry) { int sum = carry; if (l1) { sum += l1->val; l1 = l1->next; } if (l2) { sum += l2->val; l2 = l2->next; } carry = sum / 10; *node = malloc(sizeof(struct ListNode)); (*node)->val = sum % 10; (*node)->next = NULL; node = &((*node)->next); } return head; }
说明：
在C语言中，初始化头结点和当前处理结点：使用head变量来记录结果链表的头部，用node指针变量指向当前链表节点的地址，初始指向头结点地址。
遍历两个链表：当l1、l2或carry（进位）非空时，循环继续。每一步计算当前和及进位。
更新节点与进位：分别从l1和l2取值相加，再加上之前的进位值。计算后得到新的进位值和当前节点的值。
构建结果链表：为当前和的余数创建新节点，连接到结果链表末尾。
返回结果：返回头结点head。
C++版本
C++的实现更为简洁，主要是因为C++具备自动内存管理和类的特性，使得代码更易写和理解。
#include <iostream> class ListNode { public: int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *head = new ListNode(0), *node = head; int carry = 0; while (l1 || l2 || carry) { int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry; carry = sum / 10; node->next = new ListNode(sum % 10); node = node->next; if (l1) l1 = l1->next; if (l2) l2 = l2->next; } ListNode *toDelete = head; head = head->next; delete toDelete; // 删除哑节点 return head; }
说明
使用哑节点：这里创建了一个哑节点head来简化边界条件处理，便于在链表前添加节点。实际返回的是head->next。
处理两个链表和进位：循环继绀直到l1、l2和carry都处理完毕。在每一步，计算当前位置的值和新的进位。
添加新节点：根据每一步计算的结果创建新节点并链接到结果链表。
清理哑节点：在返回结果前，删除初始化时创建的哑节点。
Python3
在Python中，可以使用递归实现链表的相加。Python中链表节点通常通过类来实现，下面是一个示例：
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def addTwoNumbers(l1, l2, carry=0): if not l1 and not l2 and not carry: return None val1 = l1.val if l1 else 0 val2 = l2.val if l2 else 0 carry, out = divmod(val1 + val2 + carry, 10) currentNode = ListNode(out) currentNode.next = addTwoNumbers(l1.next if l1 else None, l2.next if l2 else None, carry) return currentNode
Go语言
在Go语言中，链表节点通常通过结构体来实现，下面是一个递归实现链表相加的示例：
type ListNode struct { Val int Next *ListNode } func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { return addTwoNumbersRecursive(l1, l2, 0) } func addTwoNumbersRecursive(l1 *ListNode, l2 *ListNode, carry int) *ListNode { if l1 == nil && l2 == nil && carry == 0 { return nil } val1, val2 := 0, 0 if l1 != nil { val1 = l1.Val } if l2 != nil { val2 = l2.Val } sum := val1 + val2 + carry newNode := &ListNode{Val: sum % 10} if l1 != nil || l2 != nil || sum >= 10 { if l1 != nil { l1 = l1.Next } if l2 != nil { l2 = l2.Next } newNode.Next = addTwoNumbersRecursive(l1, l2, sum/10) } return newNode }
说明
请注意，在Go语言中，通常使用指针来操作链表节点，以便能够修改链表的结构。在上面的代码中，
addTwoNumbers函数接收两个*ListNode类型的参数，即链表的头节点指针，并返回一个新的链表头节点指针。递归函数
addTwoNumbers计算当前节点的和，并递归地处理剩余节点。在递归调用中，我们传递了下一个节点的指针，并在每个递归步骤中处理当前节点的和。carry函数用于处理链表尾部可能出现的进位。printList
函数用于打印链表，它遍历链表并打印每个节点的值，直到链表末尾。 在main函数中，我们创建了两个示例链表l1和l2，然后调用addTwoNumbers函数计算它们的和，并使用printList`函数打印结果链表。
复杂度分析
- 时间复杂度：O(max(m, n))，其中m和n分别为两个链表的长度。每个节点最多被遍历一次。
- 空间复杂度：O(max(m, n))。由于使用了递归，函数调用的深度最坏情况下是链表的长度。因此，递归会占用与链表长度相同的栈空间。注意，这并不包括创建结果链表时分配的额外空间。如果只考虑栈空间，复杂度为O(max(m, n))；但如果同时考虑结果链表，则空间复杂度仍然是O(max(m, n))。
总结
| 方式 | 优点 | 缺点 | 时间复杂度 | 空间复杂度 | 其他 |
| 迭代方式 | - 直观易懂，易于实现 | - 代码相对较长 | O(max(m, n)) | O(max(m, n)) | m和n分别为两个链表的长度 |
| 递归方式 | - 代码简洁，易于理解 | - 可能存在栈溢出风险（链表过长时） | O(max(m, n)) | O(max(m, n))（递归栈空间）或 O(1)（不考虑递归栈） | 递归深度受链表长度限制 |
相似题目
这些相似题目涉及到加法运算、链表操作、数组操作等，对于理解链表相加问题及其变种有一定的帮助。通过解决这些相似题目，可以加深对链表、数组等数据结构以及加法运算的理解和应用。
欢迎一键三连(关注+点赞+收藏)，技术的路上一起加油！！！代码改变世界
- 关于我：阿里非典型程序员一枚 ，记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法（公众号同名），回复暗号，更能获取学习秘籍和书籍等
