乘风破浪：LeetCode真题_002

乘风破浪：LeetCode真题_002_Add Two Numbers

一、前言

这次的题目是关于链表方面的题目，把两个链表对应节点相加，还要保证进位，每个节点都必须是十进制的0~9。因此主要涉及到链表，指针方面的知识，以及活学活用的编程能力。

二、LeetCode真题_002_Add Two Numbers

2.1 问题介绍

2.2 分析与解决

看到这样的问题，我们首先要分析清题意，之后画出一个原理图，然后就便于解决了。可以看到主要是包括了进位的问题，因此我们每一次相加的时候需要考虑到进位，并且得到的结果需要取余数作为该节点的结果，并且取整数作为下一位的进位，这里要非常注意，因为是十以内的两位数相加，因此进位最多为9+9+1=19,取整之后为1，因此没有进位则进位为零，有进位，则进位为1。

 1 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 2     ListNode dummyHead = new ListNode(0);
 3     ListNode p = l1, q = l2, curr = dummyHead;
 4     int carry = 0;
 5     while (p != null || q != null) {
 6         int x = (p != null) ? p.val : 0;
 7         int y = (q != null) ? q.val : 0;
 8         int sum = carry + x + y;
 9         carry = sum / 10;
10         curr.next = new ListNode(sum % 10);
11         curr = curr.next;
12         if (p != null) p = p.next;
13         if (q != null) q = q.next;
14     }
15     if (carry > 0) {
16         curr.next = new ListNode(carry);
17     }
18     return dummyHead.next;
19 }

下面看看我们的算法：

1 public class ListNode {
2     int val;
3     ListNode next;
4 
5     ListNode(int val) {
6         this.val = val;
7     }
8 }

使用上面的数据结构进行的算法：

 1 public class Solution {
 2 
 3     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 4 
 5         if (l1 == null) {
 6             return l2;
 7         }
 8 
 9         if (l2 == null) {
10             return l1;
11         }
12 
13         ListNode p1 = l1;
14         ListNode p2 = l2;
15         ListNode root = new ListNode(0); // 头结点
16         ListNode r = root;
17         root.next = l1;
18 
19         int carry = 0; // 初始进位
20         int sum;
21         while (p1 != null && p2 != null) {
22             sum = p1.val + p2.val + carry;
23             p1.val = sum % 10; // 本位的结果
24             carry = sum / 10; // 本次进位
25 
26             r.next = p1;
27             r = p1; // 指向下一个相加的结点
28             p1 = p1.next;
29             p2 = p2.next;
30 
31         }
32 
33         if (p1 == null) {
34             r.next = p2;
35         } else {
36             r.next = p1;
37         }
38 
39         // 最后一次相加还有进位
40         if (carry == 1) {
41             // 开始时r.next是第一个要相加的结点
42             while (r.next != null) {
43                 sum = r.next.val + carry;
44                 r.next.val = sum % 10;
45                 carry = sum / 10;
46                 r = r.next;
47             }
48 
49             // 都加完了还有进位，就要创建一个新的结点
50             if (carry == 1) {
51                 r.next = new ListNode(1);
52             }
53         }
54 
55         return root.next;
56     }
57 }

三、总结

系统给出的算法是比较不错的，不但简单而且整洁，便于理解，并且考虑到了所有的可能情况，值得我们去学习和模仿。