Add Two Numbers

发表于 |

2. 链表两数相加

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.

1
2
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

SOL

直接对两个链表进行遍历(或者说对节点直接进行遍历操作而非单纯的从链表进行),复杂度是O(n)

难点在于

  • 链表的使用
  • 结构体中值和方法的调用
  • 对于加法各种情况的处理
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
/**
 * Definition for singly-linked list.
 * public class ListNode { <-注意这里是list node而非linked list
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode resultList = new ListNode(0);//由于不能new空node，所以任意赋值，返回时从下一个节点返回值即可
        ListNode t1 = l1;
        ListNode t2 = l2; 
        //ListNode t1 = l1, t2 = l2; 
        ListNode t3 = resultList;
        int digitSum = 0;
        while(t1 != null || t2 !=null){
            if (t1!=null){
                digitSum =digitSum + t1.val; //digitSum += t1.val
                t1=t1.next;//错误写法：t1=t1.next()
            }
            if(t2!=null){//注意t2和t1不要写成嵌套，是错误的逻辑
                    digitSum += t2.val;
                    t2=t2.next;
            } 
            t3.next = new ListNode(digitSum % 10);//这里要记得取余 注意这句是赋值给.next，且new了一个新node并赋值
            t3 = t3.next;
            digitSum = digitSum / 10; //传到下一位的进位，取商 digitSum/=10;
        }
        //别忘了最后一位carry上1的情况！
        if (digitSum == 1){
            t3.next = new ListNode(1);
        }
        return resultList.next;//这里直接把被copy的resultList.next返回，实际在队列中运算的是t3
    }
}

做这道题的时候还注意了一下java for each的用法:
在Java核心技术I-79页提出for each循环的语句格式为:

1
for (variable : collection) statement

定义一个变量用于暂存集合中的每一个元素,并执行相应的语句(或语句块).
Collection这一集合表达式必须是一个数组或者是一个实现了Iterable接口的类对象(例如ArrayList)