继续第二道题目,下面是问题描述:
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
这个问题比较简单,基本上解题思路是比较清晰的。输入是两个链表,链表的元素都是单个数字(0-9),要求将两个列表的相应节点数字相加,并作为结果链表返回。
这个题咋看可以马上开始解答,但是在此之前还是有一些需要注意的地方。第一点是,题目并没有说明链表的长度,所以 A 和 B 两个链表可能不一定相同长度,那么如果一个链表更长,那么相加怎么处理呢?这里就考虑直接返回即可,相当于+0。第二点是,如果相加溢出怎么处理,其实题目的例子里面已经很清晰了,溢出会发生进位,依次向后处理。第三点是,如果最后一位发生进位呢,这点容易被遗忘,需要新增一个节点。
下面是具体的代码:
// Problem 2. Add Two Numbers // URL: https://leetcode.com/problems/add-two-numbers/tabs/description // ListNode defines a singly-linked list type ListNode struct { Val int Next *ListNode } func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode { head := &ListNode{0, nil} // sentinel node carry := 0 // carray bit for tail := head; l1 != nil || l2 != nil || carry != 0; tail = tail.Next { sum := carry if l1 != nil { sum += l1.Val l1 = l1.Next } if l2 != nil { sum += l2.Val l2 = l2.Next } tail.Next, carry = &ListNode{sum % 10, nil}, sum/10 } return head.Next // discard sentinel node }