問題：?https://leetcode.com/problems/add-two-numbers-ii/#/description

思路：該題與“415. Add Strings”類似，都需要先將原來的數(shù)字序列翻轉(zhuǎn)，然后就轉(zhuǎn)化成了跟“2. Add Two Numbers”類似的問題，進而就容易解決多了。

但是本題又規(guī)定不允許對原來的鏈表進行翻轉(zhuǎn)，所以可以采用其他的方式曲線救國。這里可以利用棧的后進先出的特性，來變相實現(xiàn)輸入鏈表的翻轉(zhuǎn)。

Java實現(xiàn)代碼如下：

1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 public class Solution { 10 public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 11 // 使用推薦的Deque來代替舊的Stack 12 Deque<Integer> stack1 = new LinkedList<>(); 13 Deque<Integer> stack2 = new LinkedList<>(); 14 15 // 使用棧對兩個輸入鏈表進行翻轉(zhuǎn) 16 for(ListNode p = l1; p != null; p = p.next) { 17 stack1.addFirst(p.val); 18 } 19 for(ListNode p = l2; p != null; p = p.next) { 20 stack2.addFirst(p.val); 21 } 22 23 int carry = 0; // 進位 24 ListNode result = null; 25 while(stack1.size() > 0 || stack2.size() > 0) { 26 int sum = 0; 27 // 如果第一個鏈表里的對應(yīng)位上還有數(shù) 28 if(stack1.size() > 0) { 29 sum += stack1.removeFirst(); 30 } 31 // 如果第二個鏈表里的對應(yīng)位上還有數(shù) 32 if(stack2.size() > 0) { 33 sum += stack2.removeFirst(); 34 } 35 sum += carry; 36 ListNode node = new ListNode(sum % 10); 37 node.next = result; 38 result = node; 39 carry = sum / 10; 40 } 41 // 如果最高位相加后還有進位 42 if(carry > 0) { 43 ListNode node = new ListNode(carry); 44 node.next = result; 45 result = node; 46 } 47 48 return result; 49 } 50 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/seagoo/p/6770008.html

總結(jié)

以上是生活随笔為你收集整理的[Leetcode] 445. Add Two Numbers II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。