题目:给定两个表示非负整数的非空链表。链表中的数字以相反的顺序存储,并且每个节点都包含一个数字。将两个链表的数字相加,并将求得的和以链表的形式返回。
例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 0 -> 8
说明: 342 + 465 = 807
题解:
-
链表中数字以反序存储
-
两个链表相加存在两种可能
- 两个链表长度相等
- 其中一个链表长度大于另外一个链表
-
若两个链表长度相等,且两个链表的最高位相加之和大于10,即有进位,应为其创建新的节点。
例如: 50 + 61,其中最高位相加之和为11,即进位为1,返回的链表应为 1 -> 1 -> 1
题解代码如下:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode pre = new ListNode(0);
// 头结点
ListNode head = pre;
int carry = 0;
// 存在三种情况,l1的长度等于l2的长度,或者一长一短,还有最后节点遍历完之后,还存在值应为其创建节点
while (l1 != null || l2 != null || carry != 0) {
ListNode cur = new ListNode(0);
int sum = ((l1 == null) ? 0 : l1.val) + ((l2 == null) ? 0 : l2.val) + carry;
cur.val = sum % 10;
carry = sum / 10;
pre.next = cur;
pre = cur;
l1 = (l1 == null) ? l1 : l1.next;
l2 = (l2 == null) ? l2 : l2.next;
}
return head.next;
}
}