每天一道公司算法真题，讲解解题思路与各种算法实现；欢迎大家点评或者说出你的解题想法，或评论想让我讲解哪道题！

题目

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

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

你可以假设除了数字 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]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers/

思路

两个数相加，一般是从低位到高位，同位置数字相加，如果有进位，进位需要与高位再进行相加；

所以，可以采用此简单算法，同位相加后，用新节点保存个位数值，用进位变量保存十位数值即可；

考虑存储空间问题，和是否可以改变原有链表数据情况，可以有2种算法实现：

1. 不可改变原有链表数据情况下，新链表的所有节点都是新生成的；
2. 可以改变原有链表数据情况下，新链表的节点可以复用原有链表的节点；

算法实现

package com.nobody;

/**
 * 节点类
 */
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; } @Override public String toString() { return "ListNode{" + "val=" + val + '}'; }
}


/**
 * @Description 给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。
 * 请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字0之外，这两个数都不会以0开头。
 * 原题链接：https://leetcode-cn.com/problems/add-two-numbers/
 * @Author Mr.nobody
 * @Date 2021/1/22
 * @Version 1.0
 */
class Solution { // 新链表的每个节点都是新生成（不可以改变原有链表数据的情况下） public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { // 表头，主要为后面连接下一个节点保持同样操作 ListNode headNode = new ListNode(); // 游标 ListNode cursor = headNode; // 进位 int temp = 0; // 同时遍历2个链表的所有数据，同时是为了保证2个链表的相同位置数据进行相加处理 while (null != l1 || null != l2 || 0 != temp) { // 当前节点（位数）不为空 if (null != l1) { // 加上此节点数值 temp += l1.val; // 指向下一个节点 l1 = l1.next; } if (null != l2) { // 加上此节点数值 temp += l2.val; // 指向下一个节点 l2 = l2.next; } // 生成新节点，保留相加后的个位数值 cursor.next = new ListNode(temp % 10); // 游标指向新链表的新节点 cursor = cursor.next; // 保留相加后十位数值(即进位) temp = temp / 10; } // 返回实际表头 return headNode.next; } // 利用原有链表的节点，节省存储空间（前提是可以改变原有链表的数据） public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) { // 表头，主要为后面连接下一个节点保持同样操作 ListNode headNode = new ListNode(); // 游标 ListNode cursor = headNode; // 进位，保存每次低位2个数相加后的进位 int temp = 0; // 同时遍历2个链表的所有数据，同时是为了保证2个链表的相同位置数据进行相加处理 while (null != l1 || null != l2) { // 当前节点（位数）不为空 if (null != l1) { // 加上此节点数值 temp += l1.val; // 当前节点的值已经没用，可以利用此节点作为新的链表的节点，节省存储空间(如果l2节点不为空，会被l2节点代替) cursor.next = l1; // 指向下一个节点 l1 = l1.next; } if (null != l2) { // 加上此节点数值 temp += l2.val; // 当前节点的值已经没用，可以利用此节点作为新的链表的节点，节省存储空间 cursor.next = l2; // 指向下一个节点 l2 = l2.next; } // 游标指向新链表的新节点 cursor = cursor.next; // 保留相加后的个位数值 cursor.val = temp % 10; // 保留相加后十位数值(即进位) temp = temp / 10; } // 如果最后进行不为空，需要加上此进位 if (0 != temp) { cursor.next = new ListNode(temp); } // 返回实际表头 return headNode.next; } public static void main(String[] args) { ListNode l1 = new ListNode(0); l1.next = new ListNode(1); l1.next.next = new ListNode(8); // 打印原有链表1 ListNode l1temp = l1; while (null != l1temp) { System.out.print(l1temp + " "); l1temp = l1temp.next; } System.out.println(); ListNode l2 = new ListNode(0); l2.next = new ListNode(9); // 打印原有链表2 ListNode l2temp = l2; while (null != l2temp) { System.out.print(l2temp + " "); l2temp = l2temp.next; } System.out.println(); // 打印相加后新链表 ListNode newNode = addTwoNumbers1(l1, l2); while (null != newNode) { System.out.print(newNode + " "); newNode = newNode.next; } }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
  
88
  
89
  
90
  
91
  
92
  
93
  
94
  
95
  
96
  
97
  
98
  
99
  
100
  
101
  
102
  
103
  
104
  
105
  
106
  
107
  
108
  
109
  
110
  
111
  
112
  
113
  
114
  
115
  
116
  
117
  
118
  
119
  
120
  
121
  
122
  
123
  
124
  
125
  
126
  
127
  
128
  
129
  
130
  
131
  
132
  
133
  
134
  
135
  
136
  
137
  
138
  
139
  
140
  
141
  
142
  
143
  
144
 

输出结果：

ListNode{val=0} ListNode{val=1} ListNode{val=8} 
ListNode{val=0} ListNode{val=9} 
ListNode{val=0} ListNode{val=0} ListNode{val=9} 

  

 

  
1
  
2
  
3
 

Leetcode执行结果：

上下篇

上一篇：思路讲解与算法实现 LeetCode - 两数之和

下一篇：思路讲解与算法实现 LeetCode - 数组形式的整数加法

文章来源: javalib.blog.csdn.net，作者：陈皮的JavaLib，版权归原作者所有，如需转载，请联系作者。

原文链接：javalib.blog.csdn.net/article/details/112979758