题目描述

给你两个 非空 的链表，表示两个非负的整数。
它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

将两个数相加，并以相同形式返回一个表示和的链表。

除数字 0 之外，这两个数都不会以 0 开头。

1.模拟（加法器）

1.1思路

时间复杂度：O( max(m ，n) )
空间复杂度：O(1)

笔者疑惑：官方给出的程序中，答案链表所占空间大小应为 max(m,n) 或 max(m,n) + 1，所以此处笔者觉得该算法空间复杂度应为 O(max(m,n))，求解惑。

由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。

我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。
具体而言，如果当前两个链表处相应位置的数字为 n1、n2，进位值为 carry，则它们的和为 n1 + n2 +carry；
其中，答案链表处相应位置的数字为 (n1 + n2 + carry) mod 10，而新的进位值为 ⌊(n1 + n2 + carry) / 10⌋。

如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0。

此外，如果链表遍历结束后，有 carry > 0，还需要在答案链表的后面附加一个节点，节点的值为 carry。

1.2代码

1.C

// 注：前面应该还有定义链表结构体的步骤
// l1：链表1，l2：链表2
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {struct ListNode *head = NULL, *tail = NULL;	// 答案链表的头 [head] 尾 [tail] 结点int carry = 0;	// 加法进位while (l1 || l2) {	// l1 和 l2 只要有一个没有遍历结束就一直执行此循环int n1 = l1 ? l1->val : 0;	// n1 记录 l1 当前结点的数字，若为空则置0，否则置 l1 当前结点的值int n2 = l2 ? l2->val : 0;	// n2 记录 l2 当前结点的数字，若为空则置0，否则置 l2 当前结点的值int sum = n1 + n2 + carry;	// 相同位置之和 sum = 两链表相同位置的结点的值相加再加上仅为 carry// 下面的 if - else 语句用于将对应位置相加的值插入答案链表，因原链表为逆序，故使用尾插法if (!head) {	// 头结点为空head = tail = malloc(sizeof(struct ListNode));	// 为新结点申请空间tail->val = sum % 10;	// 尾插对应目标值tail->next = NULL;} else {	// 头结点不为空tail->next = malloc(sizeof(struct ListNode));	// 为新结点申请空间tail->next->val = sum % 10;	// 尾插对应目标值tail = tail->next;tail->next = NULL;}carry = sum / 10;	// 计算进位值 carry = ⌊(n1 + n2 + carry) / 10⌋if (l1) {	// l1 不为空，遍历 l1 的下一个结点l1 = l1->next;}if (l2) {	// l2 不为空，遍历 l2 的下一个结点l2 = l2->next;}}if (carry > 0) {	// 遍历结束后 carry > 0，则额外申请一个新结点存放 carrytail->next = malloc(sizeof(struct ListNode));tail->next->val = carry;tail->next->next = NULL;}return head;	// 返回答案链表的头结点
}

2.C++

class Solution {
public:// 注：前面应该还有定义链表结构体的步骤// l1：链表1，l2：链表2ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {// nullptr 用于避免指针赋空值容易出现的二义性问题，其本质相当于 NULLListNode *head = nullptr, *tail = nullptr;	// 答案链表的头 [head] 尾 [tail] 结点int carry = 0;	// 加法进位while (l1 || l2) {	// l1 和 l2 只要有一个没有遍历结束就一直执行此循环int n1 = l1 ? l1->val: 0;	// n1 记录 l1 当前结点的数字，若为空则置0，否则置 l1 当前结点的值int n2 = l2 ? l2->val: 0;	// n2 记录 l2 当前结点的数字，若为空则置0，否则置 l2 当前结点的值int sum = n1 + n2 + carry;	// 相同位置之和 sum = 两链表相同位置的结点的值相加再加上仅为 carry// 下面的 if - else 语句用于将对应位置相加的值插入答案链表，因原链表为逆序，故使用尾插法if (!head) {	// 头结点为空head = tail = new ListNode(sum % 10);	// 为新结点申请空间，尾插入对应目标值} else {	// 头结点不为空tail->next = new ListNode(sum % 10);	// 为新结点申请空间，尾插入对应目标值tail = tail->next;}carry = sum / 10;	// 计算进位值 carry = ⌊(n1 + n2 + carry) / 10⌋if (l1) {	// l1 不为空，遍历 l1 的下一个结点l1 = l1->next;}if (l2) {	// l2 不为空，遍历 l2 的下一个结点l2 = l2->next;}}if (carry > 0) {	// 遍历结束后 carry > 0，则额外申请一个新结点存放 carrytail->next = new ListNode(carry);}return head;	// 返回答案链表的头结点}
};

3.Java

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head = null, tail = null;int carry = 0;while (l1 != null || l2 != null) {int n1 = l1 != null ? l1.val : 0;int n2 = l2 != null ? l2.val : 0;int sum = n1 + n2 + carry;if (head == null) {head = tail = new ListNode(sum % 10);} else {tail.next = new ListNode(sum % 10);tail = tail.next;}carry = sum / 10;if (l1 != null) {l1 = l1.next;}if (l2 != null) {l2 = l2.next;}}if (carry > 0) {tail.next = new ListNode(carry);}return head;}
}

4.C#

public class Solution {public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {ListNode head = null, tail = null;int carry = 0;while (l1 != null || l2 != null) {int n1 = l1 != null ? l1.val : 0;int n2 = l2 != null ? l2.val : 0;int sum = n1 + n2 + carry;if (head == null) {head = tail = new ListNode(sum % 10);} else {tail.next = new ListNode(sum % 10);tail = tail.next;}carry = sum / 10;if (l1 != null) {l1 = l1.next;}if (l2 != null) {l2 = l2.next;}}if (carry > 0) {tail.next = new ListNode(carry);}return head;}
}

5.Javascript

var addTwoNumbers = function(l1, l2) {let head = null, tail = null;let carry = 0;while (l1 || l2) {const n1 = l1 ? l1.val : 0;const n2 = l2 ? l2.val : 0;const sum = n1 + n2 + carry;if (!head) {head = tail = new ListNode(sum % 10);} else {tail.next = new ListNode(sum % 10);tail = tail.next;}carry = Math.floor(sum / 10);if (l1) {l1 = l1.next;}if (l2) {l2 = l2.next;}}if (carry > 0) {tail.next = new ListNode(carry);}return head;
};

6.Golang

func addTwoNumbers(l1, l2 *ListNode) (head *ListNode) {var tail *ListNodecarry := 0for l1 != nil || l2 != nil {n1, n2 := 0, 0if l1 != nil {n1 = l1.Vall1 = l1.Next}if l2 != nil {n2 = l2.Vall2 = l2.Next}sum := n1 + n2 + carrysum, carry = sum%10, sum/10if head == nil {head = &ListNode{Val: sum}tail = head} else {tail.Next = &ListNode{Val: sum}tail = tail.Next}}if carry > 0 {tail.Next = &ListNode{Val: carry}}return
}