題目描述

假設鏈表中每一個節點的值都在 0 - 9?之間，那么鏈表整體就可以代表一個整數。

給定兩個這種鏈表，請生成代表兩個整數相加值的結果鏈表。

例如：鏈表 1?為 9->3->7，鏈表 2?為 6->3，最后生成新的結果鏈表為 1->0->0->0。

?

示例1

輸入

[9,3,7],[6,3]

返回值

{1,0,0,0}

?

方案一:

1、將兩個鏈表逆序，這樣就可以依次得到從低到高位的數字

2、同步遍歷兩個逆序后鏈表，相加生成新鏈表，同時關注進位

3、當兩個鏈表都遍歷完成后，關注進位。

4、 將兩個逆序的鏈表再逆序一遍，調整回去

package datastructure;public class AddInListMe {/**** @param head1 ListNode類* @param head2 ListNode類* @return ListNode類*/public ListNode addInList (ListNode head1, ListNode head2) {head1 = reverseList(head1);head2 = reverseList(head2);int ca = 0;int n1 =0;int n2 =0;int n =0;ListNode c1 = head1;ListNode c2 = head2;ListNode node = null;ListNode pre = null;while(c1 !=null || c2!=null){n1 = c1 != null ? c1.val:0;n2 = c2 != null ? c2.val:0;n = n1+n2+ca;pre= node;node = new ListNode(n % 10); // 余數node.next=pre;ca=n/10;c1=c1 != null ? c1.next : null;c2=c2 != null ? c2.next : null;}if(ca == 1){pre=node;node = new ListNode(1);node.next = pre;}reverseList(head1);reverseList(head2);return node;}public ListNode reverseList(ListNode head){ListNode pre = null;ListNode next = null;while(head!=null){next=head.next;head.next=pre;pre=head;head=next;}return pre;} }

?

方案二:

? ?能把數據順序反過來的數據結構，那不就是棧嘛，我們可以先將兩個鏈表中的數存儲在棧中，計算的時候依次出棧，再加上一個標志位?carry，我們就能做到計算個位的和，并向十位進位，再計算十位的和，并向百位進位，以此類推。。。

public ListNode addInList(ListNode head1, ListNode head2) {Stack<Integer> s1 = new Stack<>();Stack<Integer> s2 = new Stack<>();int ca = 0;while(null != head1){s1.push(head1.val);head1 = head1.next;}while(null != head2){s2.push(head2.val);head2 = head2.next;}int c1 = 0;int c2 = 0;int ret = 0;ListNode pre;ListNode node=null;while(!s1.isEmpty() || !s2.isEmpty()){c1 = 0;c2 = 0;if(!s1.isEmpty()){c1 = s1.pop();}if(!s2.isEmpty()){c2 = s2.pop();}ret = c1 + c2 + ca;pre = node;node = new ListNode(ret%10);node.next = pre;ca = ret/10;}if(1 == ca){pre = node;node = new ListNode(1);node.next = pre;}return node;}

?

總結

以上是生活随笔為你收集整理的常考数据结构与算法:两个链表生成相加链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。