【LeetCode-面試算法經典-Java實現】【002-Add Two Numbers (單鏈表表示的兩個數相加)】...

【002-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

題目大意

　　有兩個單鏈表。代表兩個非負數，每個節點代表一個數位。數字是反向存儲的。即第一個結點表示最低位。最后一個結點表示最高位。求兩個數的相加和，而且以鏈表形式返回。

解題思路

　　對兩個鏈表都從第一個開始處理，進行相加，結果再除以10求商。作為下一位相加的進位。同一時候記錄余數，作為本位的結果，一直處理，直到全部的結點都處理完。

代碼實現

 /*** 002-Add Two Numbers (單鏈表表示的兩個數相加)* @param l1 第一個數* @param l2 第二個數* @return 結果*/public ListNode addTwoNumbers(ListNode l1, ListNode l2) {if (l1 == null) {return l2;}if (l2 == null) {return l1;}ListNode p1 = l1;ListNode p2 = l2;ListNode root = new ListNode(0); // 頭結點ListNode r = root;root.next = l1;int carry = 0; // 初始進位int sum;while (p1 != null && p2 != null) {sum = p1.val + p2.val + carry;p1.val = sum % 10; // 本位的結果carry = sum / 10; // 本次進位r.next = p1;r = p1; // 指向最后一個相加的結點p1 = p1.next;p2 = p2.next;}if (p1 == null) {r.next = p2;} else {r.next = p1;}// 最后一次相加還有進位if (carry == 1) {// 開始時r.next是第一個要相加的結點while (r.next != null) {sum = r.next.val + carry;r.next.val = sum % 10;carry = sum / 10;r = r.next;}// 都加完了還有進位。就要創建一個新的結點if (carry == 1) {r.next = new ListNode(1);}}return root.next;}
}

評測結果

　　點擊圖片，鼠標不釋放，拖動一段位置，釋放后在新的窗體中查看完整圖片。

特別說明

歡迎轉載，轉載請注明出處【http://blog.csdn.net/DERRANTCM/article/details/46905467】