【鏈表】Add Two Numbers

題目：

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.

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

思路：

從左到右相加，記錄進位值。

注意：兩個鏈表不同長度，及鏈表相加后也要檢驗進位是否為0。

/*** Definition for singly-linked list.* function ListNode(val) {*     this.val = val;*     this.next = null;* }*/
/*** @param {ListNode} l1* @param {ListNode} l2* @return {ListNode}*/
var addTwoNumbers = function(l1, l2) {var carrybit=0,tempHead=new ListNode(0);var p=tempHead;while(l1&&l2){l1.val+=l2.val+carrybit;carrybit=l1.val/10;l1.val=l1.val%10;p.next=l1;p=p.next;l1=l1.next;l2=l2.next;}var lp=(l1==null?l2:l1);while(lp){if(carrybit==0){p.next=lp;break;}else{lp.val+=carrybit;carrybit=lp.val/10;lp.val=lp.val%10;p.next=lp;p=p.next;}lp=lp.next;}if(carrybit!=0){p.next=new ListNode(carrybit);}return tempHead.next;
};

?

如果鏈表存儲整數時，高位在前，該如何處理。

1、最簡單的想法是，可以先把鏈表反轉，然后調用上面的算法，最后把結果反轉。

2、可不可以從高位向低位方向處理呢？我們知道進位是從低位傳向高位的，如果從高位向低位方向計算，當計算到某一位需要進位時，有沒有辦法知道該進位傳遞到前面的哪一位呢？從以下幾個例子來看：

從最高位到最低位我們依次記為第 1,2…,7位。圖中紅色標記的位置是：下一次需要進位時，進位的1放置的位子

第1位相加，結果為12，需要進位，這個進位放到第0位；同時標記第1位為下一次的進位標志

第2位相加，結果為3，不需要進位；標記第2位為下一次進位標志

第3位相加，結果為3，不需要進位；標記第3位為下一次進位標志

第4位相加，結果為9，不需要進位；此時進位標志不需要移動，因為9加上一個進位后還要繼續向前進位

第5位相加，結果為9，不需要進位；此時進位標志不需要移動，因為9加上一個進位后還要繼續向前進位

第6位相加，結果為14，需要進位，這個進位放到前面標記的第3位上，同時把第4位和第5位置0，標記第6位為下一次進位標志

第7位同上

?

所以綜上所述，從高位往低位計算加法時，規則是：

一、如果當前位沒有進位：（1）如果當前位的和小于9，則把改位設置成下一次進位標志（2）如果和等于9，進位標志不變

二、如果當前位有進位：把進位的1加到前面標志的位子上，同時把標志位和當前位之間的位全部置0（因為他們之間的位肯定全部都是9），把當前位設置成進位標志

?

上面我們舉例的兩個加數長度一致，如果長度不相同，則要先處理較長的整數的前面多出的部分。

?

我們把這一題leetcode的輸入反轉，測試代碼如下：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {l1 = reverseList(l1);l2 = reverseList(l2);int n1 = lenList(l1), n2 = lenList(l2);if(n1 < n2)//l1 指向較長的鏈表
        {swap(n1,n2);swap(l1,l2);}//carryLoc是下一次出現進位時，進位的1將要放置的位子，pre指向當前結果鏈表的最后一個節點//p1,p2分別是當前處理的l1,l2節點//由于加數的最高位有可能進位，所以添加一個新的節點newHeadListNode *newHead = new ListNode(0), *carryLoc = newHead, *pre = newHead, *p1 = l1;for(int i = 0; i < n1-n2; i++)//處理l1高位長出的部分
        {if(p1->val < 9)carryLoc = p1;pre->next = p1;pre = p1;p1 = p1->next;}ListNode* p2 = l2;while(p1 != NULL){pre->next = p1;pre = p1;p1->val += p2->val;if(p1->val > 9){carryLoc->val += 1;for(carryLoc = carryLoc->next; carryLoc != p1; carryLoc = carryLoc->next)//carryLoc到p1之間的節點全部置0carryLoc->val = 0;p1->val -= 10;}if(p1->val < 9)carryLoc = p1;p1 = p1->next;p2 = p2->next;}if(newHead->val != 0)return reverseList(newHead);else return reverseList(newHead->next);}//反轉鏈表ListNode *reverseList(ListNode *l1){ListNode *p = l1->next, *pre = l1;l1->next = NULL;while(p){ListNode *tmp = p->next;p->next = pre;pre = p;p = tmp;}return pre;}//求鏈表長度int lenList(ListNode *head){int res = 0;while(head){res++;head = head->next;}return res;}
};

?

后面轉載自：http://www.cnblogs.com/TenosDoIt/p/3735362.html