【LeetCode Top 100】2. Add Two Numbers【Medium】【JAVA】

喜欢ヅ旅行 2021-09-20 22:00 167阅读 0赞

## 1. 题目 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]

## 2. 题意 ##

即两个链表代表两个整数，相加的结果也放到一个链表中。

## 3. 思路 ##

本题虽然是中等难度，但相对容易。对于两个整数相加，我们正常的做法就是列竖式，从低位开始相加，到高位，超过十则向前进一。而链表刚好是从数的低位指向高位，因此只需按照正常两个数相加的方式，从低位（即链表头）进行相加的方式进行，只需注意进位的情况，以及最后可能数位会长于两个加数的情况即可。

## 4. 解题代码 ##

public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
    		// 这里使用哨兵节点，好处在下面讲
            ListNode result = new ListNode(0);
            ListNode head = result;
            // add 表示是否进位
            int add = 0, a1, a2;
            
            // 循环条件，遍历到两条链表均到达链尾
            while (l1 != null || l2 != null) { 
                // 当一条链结束时，接下来的循环中，该链获取的值均为 0
                if (l1 != null) { 
                    a1 = l1.val;
                    l1 = l1.next;
                } else { 
                    a1 = 0;
                }
                if (l2 != null) { 
                    a2 = l2.val;
                    l2 = l2.next;
                } else { 
                    a2 = 0;
                }
                
                // 计算当前位的值
                head.next = new ListNode((a1 + a2 + add) % 10);
                // 判断是否需进位
                add = (a1 + a2 + add) / 10;
                head = head.next;
            }
            
            // 注意最后可能需要再进一位
            if (add == 1) { 
                head.next = new ListNode(1);
            }
    
            return result.next;
        }

## 5. 运行结果 ##

![在这里插入图片描述][20191028000442304.png]

## 6. 其他 ##

对于哨兵节点，如下图，黄色代表我们所要求的链表，而蓝色为哨兵节点，另外用一个head指向哨兵节点，则当获取head->next的时候，我们即可获得我们所需的聊表的头节点  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 1]  
这么做的好处在于，虽然多了一个节点的开销，但我们少了对链表是否为空，即头节点是否位空的判断，可提升性能。

## 7. 相关链接 ##

[本题代码的github链接][github]  
[其他 LeetCode 题目解析][LeetCode]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70]: /images/20210920/97c46a4de50e4ef196c5800ab15e17e2.png
[20191028000442304.png]: /images/20210920/dda8bff7bc95417293f8163290d6f240.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0FwcGx5aW5n_size_16_color_FFFFFF_t_70 1]: /images/20210920/20ee9114b9324f8ba2896dbecbdd430d.png
[github]: https://github.com/Parallelline1996/Leetcode/blob/master/Problems/src/main/java/page1/N2_AddTwoNumbers.java
[LeetCode]: https://blog.csdn.net/applying/category_9629399.html