04 Nov 2016 | LeetCode
You are given two linked lists representing two non-negative numbers. 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.
给出代表两个非负数的两个链表。数字存储在相反的顺序并且它们的每一个节点包含单个数字。添加两个数字，并返回它作为一个链表。
- Difficulty: Medium
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
在学C语言的时候学到过一种数据结构“链表”，即linked-list，讲C语言时老师一带而过，后来加了程设为了做一道linked-list实现增删改查的题，把浙大翁恺老师的C语言程序设计中链表这一块翻来覆去看了无数遍。可惜抄了许多代码，印象也不甚深刻。只是在C语言中是通过指针和struct，在Java中通过属性，Java有LinkedList数据类型，是一个双向链表。
此处定义一个单向链表节点的类ListNode。首先初始化Node的和为sum=0，判断l1和l2是否为空，若不为空，则将其Node值加到sum上，实现了两个linked-list的对应节点相加。初始化一个初值为0的节点ret，即链表的根，并把它赋给一个新节点临时变量cur，将sum取余的值赋给cur的值，cur即储存链表的最后一个节点。让sum等于sum的十位数。判断两个链表和sum有一个不为0时，让cur指向一个新的val为0的节点，并且继续循环，此时之前的sum继续与两个链表的值相加，实现进位。当它们都为0时跳出循环，返回根ret，即返回了整个链表。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode ret=new ListNode(0);
ListNode cur=ret;
int sum=0;
while(true){
if(l1!=null){
sum+=l1.val;
l1=l1.next;
}
if(l2!=null){
sum+=l2.val;
l2=l2.next;
}
cur.val=sum%10;
sum/=10;
if(l1!=null || l2!=null || sum!=0){
cur=(cur.next=new ListNode(0));
}
else
break;
}
return ret;
}
}此处算法思想和上述Java代码是一样的，注意ret和cur指向的同一个地址，所以改变cur，ret也会改变。
另外，在C里要给结构体ListNode分配内存空间，否则会报错。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
struct ListNode *ret=(struct ListNode*) (malloc(sizeof(struct ListNode))); // 定义返回Node
struct ListNode *cur=ret; //定义临时变量cur，指向最后一个Node
ret->val=0;
ret->next=NULL;
int sum=0;
while(true){
if(l1!=NULL){
sum+=(l1->val);
l1=(l1->next);
}
if(l2!=NULL){
sum+=(l2->val);
l2=(l2->next);
}
cur->val=sum%10; //求出相加的值赋给cur->val
sum/=10; //进位
if(l1!=NULL || l2!=NULL ||sum!=0){
(cur->next)=(struct ListNode*)(malloc(sizeof(struct ListNode)));
(cur->next)->val=0;
(cur->next)->next=NULL;
cur=cur->next; //让cur指向cur->next
}
else break;
}
return ret;
}