【2017.11.29】2.Add Two Numbers

2.1 non-非

non- 无，非，不
ag:The countries in the region signed a non-aggression pact。在该地区的国家签订了一个互不侵犯的条约

non-empty :非空的

non-negatice:非负的

2.2 node：节点

表示链表中的结点。

c.pseudcode 伪代码

executable pseudcode 可执行的伪代码、

伪代码是一种算法描述语言。使用伪代码的算法可以同意地以任何一种变成语言（pascal，c，java）实现。

因此伪代码必须结构清晰，代码简单，可读性好，并且类似自然语言。

2.3 a linked list：链表

在计算机科学中，链表是数据元素的线性集合，其中线性顺序不是由他们在存储器中的物理位置给出的。相反，每一个元素指向下一个，节点组成的数据结构，这些节点一起表示一个序列。在最简单的形势下，每个节点由数据和引用组成。
(　o=^•ェ•)o　┏━┓
你可以把链表想象成火车，节点就是其中一节节的车厢，通过通道和前后车厢相连。因为节点中要包含数据、只想前后车厢的链接，所以一般是复合型的结构体。

链表，其节点包含两个字段：整数值和到下一个节点的链接。最后一个节点链接到用于表示列表结尾的终止符。

2.4 java-dummy head 假表头

有了dummy head之后，所有的节点都变成了拥有前置节点的节点了，所以就不用担心处理头结点这个特殊的情况了。而且你最后需要返回的仅仅是dummy.next，不用发功夫保住你的头节点了。

2.5 Initialize初始化

2.6 set-node-value ：设置节点的值

2.7 listNode 链表

//单链表数据结构
public ListNodeP{Object element;ListNode next;ListNode(Obeject o,ListNode n){element=o;next=n;}ListNode(Object o){this(o,null);}
}

2.Add Two Number

题目：

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.

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

解析：

Intution:(直观解释)

Keep track of the carry using a variable and simulate digits-by-digits sum starting from the head of list, which contains the least-significant digit.

Algorithm(算法)：

The pseudocode(伪代码) is as following:

• Initialize current node to dummy head(假表头) of the returning list.
• Initialize carry to 0.
• Initialize p and q to head of l1 and l2 respectively(分别地).
• Loop through lists(通过列表循环) l1 and l2 until you reach both ends（知道两端）.
  
  • Set x to node p’s value. If p has reached the end of l1, set to 0.
  • Set y to node q’s value. If q has reached the end of l2, set to 0.
  • Set sum = x + y + carry.
  • Update carry = sum / 10.
  • Create a new node with the digit value of (sum mod 10)and set it to current node’s next, then advance current node to next.
  • Advance both pp and qq.
• Check if carry = 1, if so append a new node with digit 1 to the returning list.
• Return dummy head’s next node.
  Note that we use a dummy head to simplify the code. Without a dummy head, you would have to write extra conditional statements to initialize the head’s value.
  我们实用虚拟头来简化代码，没有虚拟头，你不得不编写额外的条件语句来初始化头的值。

Take extra caution of the following cases:

code：

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode(int x) { val = x; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {//初始化虚拟表头为0ListNode dummyHead = new ListNode(0);//给p，q 为表头数据，curr为我们最终求的链表，carry即为进位值，初始化为0ListNode p = l1, q = l2, curr = dummyHead;int carry = 0;while(p!=null || q!=null){int x = (p!= null) ? p.val : 0;int y = (q!= null) ? q.val : 0;int sum = carry + x + y;//carry更新进位carry = sum / 10;//为链表创建新的节点，节点初始值为sum的个位数，赋值到ListNode的结构体成员next中。//将curr.next加入链表中curr.next = new ListNode(sum % 10);curr = curr.next;//向后移动链表if(p!=null) p=p.next;if(q!=null) q=q.next;}//判断最后一个进位if(carry>0){curr.next = new ListNode(carry);}//返回虚拟表头的下一个节点return dummyHead.next;        }
}

友情链接：

wiki-linked list

leecode-解答

csdn-数据结构学习笔记之一:链表