LeetCode（2）：Add Two Numbers 两数相加

Medium！

题目描述：

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

思路：

本题的思路很简单，按照小学数学中学习的加法原理从末尾到首位，对每一位对齐相加即可。技巧在于如何处理不同长度的数字，以及进位和最高位的判断。将两个单链表表示的数字相加，再将结果用单链表表示出来。主要考察对链表的操作，对链表这种数据结构的遍历、增、删等操作应该熟练。

 1 class Solution {
 2 public:
 3     ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
 4         ListNode *res = new ListNode(-1);
 5         ListNode *cur = res;
 6         int carry = 0;
 7         while (l1 || l2) {
 8             int n1 = l1 ? l1->val : 0;
 9             int n2 = l2 ? l2->val : 0;
10             int sum = n1 + n2 + carry;
11             carry = sum / 10;
12             cur->next = new ListNode(sum % 10);
13             cur = cur->next;
14             if (l1) l1 = l1->next;
15             if (l2) l2 = l2->next;
16         }
17         if (carry) cur->next = new ListNode(1);
18         return res->next;
19     }
20 };

知识点回顾：

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。链表可以在多种编程语言中实现。像Lisp和Scheme这样的语言的内建数据类型中就包含了链表的存取和操作。程序语言或面向对象语言，如C,C++和Java依靠易变工具来生成链表。

其中存储数据元素信息的域称作数据域（设域名为data），存储直接后继存储位置的域称为指针域（设域名为next）。指针域中存储的信息又称做指针或链。

由分别表示,，…，的N 个结点依次相链构成的链表，称为线性表的链式存储表示，由于此类链表的每个结点中只包含一个指针域，故又称单链表或线性链表。

C++创建单链表的基本操作：

 1 #include <iostream>  
 2 using namespace std;  
 3 /* 创建一个单链表 */  
 4 struct ListNode{  
 5     int m_key;  
 6     ListNode* next;  
 7 };  
 8 void createList(ListNode* pHead){  
 9     ListNode* p = pHead;  
10     for (int i = 1; i < 10; ++i) {  
11         ListNode* pNewNode = new ListNode;  
12         pNewNode->m_key = i; // 将新节点的值赋值为i  
13         pNewNode->next = NULL;  
14         p->next = pNewNode; // 上一个节点指向这个新建立的节点  
15         p = pNewNode; // p节点指向这个新的节点  
16     }  
17 }  
18 int main(){  
19     ListNode* head = NULL;  
20     head = new ListNode;  
21     head->m_key = 0;  
22     head->next = NULL;  
23     createList(head);  
24   
25     return 0;  
26 }

官方解答：

问题描述：

给定两个链表分别代表两个非负整数，链表的每个结点分别存储整数的每位数字，且是逆序存储，即：数字最低位存储在链表表头，数字最高位存储在链表表尾。求解这两个整数的和并以相同的链表形式返回计算的结果。

例如：输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8

问题分析：

本题其实是一个大数相加问题，题目本身难度不大，需要考虑以下几个方面：1、设计好数据结构，反序存储数字，如数字932存储为2->3->9。

1 //结点数据结构
2 struct ListNode {
3   ListNode(int x) : val(x), next(NULL){}
4   int val;
5   ListNode *next;
6 };

链表对应结点相加时增加前一个结点的进位，并保存下一个结点的进位；
两个链表长度不一致时，要处理较长链表剩余的高位和进位计算的值；
如果最高位计算时还产生进位，则还需要添加一个额外结点。

代码实现：

 1 class Solution {
 2 public:
 3 ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
 4     ListNode preHead(0), *p = &preHead;
 5     int carry = 0;
 6     while (l1 || l2 || carry) {
 7         int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
 8         carry = sum / 10;
 9         p->next = new ListNode(sum % 10);
10         p = p->next;
11         l1 = l1 ? l1->next : l1;
12         l2 = l2 ? l2->next : l2;
13     }
14     return preHead.next;
15 };