两个链表生成相加链表算法-java实现

80 阅读 0 评论 53 点赞

我是靠谱客的博主怕黑咖啡豆，这篇文章主要介绍两个链表生成相加链表算法-java实现，现在分享给大家，希望可以做个参考。

题目描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
示例1
输入：[9,3,7],[6,3]
返回值：{1,0,0,0}

解题思路

曾经想过既然是两个链表形成的数字相加，那我把两个链表的数字都取出来分别放入两个long变量，再对其进行相加，得到的数字拆解位数放入一个新的链表不就完了，但这种做法比较low，只用到了遍历链表的知识点，好像不太入流，估计面试官看到也要鄙视我的。后来看了其他人的答案后，发现真是妙啊，思路跟我们做数学运算一样，从低位加起，保留进位，将进位低位的下一位高位处加，但我们这个链表是从左到右的顺序，所以要实现我们的数学运算，就得先翻转链表，然后再做数学运算：
a，b链表的位数一致，同时加完，那么进位的值就需要多一位数存储
a链表位数比b链表位数多n位，那么在对完b链表的位数后，a链表剩余的位数就得多n位存储，当然多的第一位的进位要加上。
b链表位数比a链表位数多n位，同理。
我在运算的过程中直接组成了结果链表，所以最后直接输出结果链表的起始节点就行了。

代码实现

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.util.*;
/*
* public class ListNode {
*
int val;
*
ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList (ListNode head1, ListNode head2) {
// write code here
head1=reverse(head1);
head2=reverse(head2);
ListNode cur=null;
int cnt=0;
while(head1!=null||head2!=null){
int val=cnt;
if(head1!=null){
val+=head1.val;
head1=head1.next;
}
if(head2!=null){
val+=head2.val;
head2=head2.next;
}
ListNode newNode=new ListNode(val%10);
if(cur!=null){
newNode.next=cur;
}
cnt=val/10;
cur=newNode;
}
if(cnt>0){
ListNode newNode=new ListNode(cnt);
newNode.next=cur;
cur=newNode;
}
return cur;
}
public ListNode reverse(ListNode node){
ListNode lastNode=null;
ListNode nextNode=null;
ListNode curNode=node;
while(curNode!=null){
nextNode=curNode.next;
curNode.next=lastNode;
lastNode=curNode;
curNode=nextNode;
}
return lastNode;
}
}