文章目录

• 一【题目类别】
• 二【题目难度】
• 三【题目编号】
• 四【题目描述】
• 五【题目示例】
• 六【题目提示】
• 七【解题思路】
• 八【时间频度】
• 九【代码实现】
• 十【提交结果】

一【题目类别】

• 链表

二【题目难度】

• 中等

三【题目编号】

• 2.两数相加

四【题目描述】

• 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
  请你将两个数相加，并以相同形式返回一个表示和的链表。
  你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

五【题目示例】

• 示例 1：
  
  输入：l1 = [2,4,3], l2 = [5,6,4]
  输出：[7,0,8]
  解释：342 + 465 = 807.

• 示例 2：
  输入：l1 = [0], l2 = [0]
  输出：[0]

• 示例 3：
  输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
  输出：[8,9,9,9,0,0,0,1]

六【题目提示】

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

七【解题思路】

• 这种题目应该作为一种类型去解，在PAT上面做过类似的题目，主要核心在于设置进位位。具体思路如下：
  ①：设置虚拟头结点，方便最后返回链表使用。并设置工作指针指向虚拟头结点。并设置进位位，初始化为0
  ②：遍历两个链表，注意这里有一个注意点，如果l1为空，设置l1的值为0，否则为l1.val。l2同理，这样的目的是防止两个链表长度不一样导致的错误
  ③：然后计算进位和当前为的值
  ④：新建结点存储新值，并链接链表
  ⑤：两链表结点后移
  ⑥：最后如果还有进位新建结点存储值，然后链接链表
  ⑦：返回虚拟头结点的下一个结点，即为结果链表头结点

八【时间频度】

• 时间复杂度：$O(n)$，其中$n$为最长链表长度
• 空间复杂度：$O(n)$，其中$n$为结果链表长度

九【代码实现】

1. Java语言版

package LinkedList;public class p2_AddTwoNumbers {    int val;    p2_AddTwoNumbers next;    public p2_AddTwoNumbers() {    }    public p2_AddTwoNumbers(int val) { this.val = val;    }    public p2_AddTwoNumbers(int val, p2_AddTwoNumbers next) { this.val = val; this.next = next;    }    public static void main(String[] args) { p2_AddTwoNumbers node1_1 = new p2_AddTwoNumbers(2); p2_AddTwoNumbers node1_2 = new p2_AddTwoNumbers(4); p2_AddTwoNumbers node1_3 = new p2_AddTwoNumbers(3); p2_AddTwoNumbers node2_1 = new p2_AddTwoNumbers(5); p2_AddTwoNumbers node2_2 = new p2_AddTwoNumbers(6); p2_AddTwoNumbers node2_3 = new p2_AddTwoNumbers(4); node1_1.next = node1_2; node1_2.next = node1_3; node2_1.next = node2_2; node2_2.next = node2_3; p2_AddTwoNumbers res = addTwoNumbers(node1_1, node2_1); while (res != null) {     if (res.next != null) {  System.out.print(res.val + "->");     } else {  System.out.print(res.val);     }     res = res.next; }    }    public static p2_AddTwoNumbers addTwoNumbers(p2_AddTwoNumbers l1, p2_AddTwoNumbers l2) { p2_AddTwoNumbers fakeNode = new p2_AddTwoNumbers(-1); p2_AddTwoNumbers curNode = fakeNode; int carry = 0; while (l1 != null || l2 != null) {     int x = (l1 == null) ? 0 : l1.val;     int y = (l2 == null) ? 0 : l2.val;     int sum = x + y + carry;     carry = sum / 10;     sum %= 10;     curNode.next = new p2_AddTwoNumbers(sum);     curNode = curNode.next;     if (l1 != null) {  l1 = l1.next;     }     if (l2 != null) {  l2 = l2.next;     } } if (carry > 0) {     curNode.next = new p2_AddTwoNumbers(carry);     curNode = curNode.next; } return fakeNode.next;    }}

2. C语言版

#includestruct ListNode{int val;struct ListNode *next;};struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){struct ListNode *fakeNode = (struct ListNode *)malloc(sizeof(struct ListNode));fakeNode->val = -1;fakeNode->next = NULL;struct ListNode *curNode = fakeNode;int carry = 0;while (l1 != NULL || l2 != NULL){int x = (l1 == NULL) ? 0 : l1->val;int y = (l2 == NULL) ? 0 : l2->val;int sum = x + y + carry;carry = sum / 10;sum %= 10;struct ListNode *tempNode = (struct ListNode *)malloc(sizeof(struct ListNode));tempNode->val = sum;tempNode->next = NULL;curNode->next = tempNode;curNode = curNode->next;if (l1 != NULL){l1 = l1->next;}if (l2 != NULL){l2 = l2->next;}}if (carry > 0){struct ListNode *tempNode = (struct ListNode *)malloc(sizeof(struct ListNode));tempNode->val = carry;tempNode->next = NULL;curNode->next = tempNode;curNode = curNode->next;}return fakeNode->next;}/*主函数省略*/

十【提交结果】

1. Java语言版
   

2. C语言版
   

全民K歌