两个链表相加

这是我之前去一家公司面试出的一道面试题，但是感觉很简单，却没有答出来，现在记录一下。两个链表的相加，这是考验java基础，数据结构基础，算法基础，以及自己的思维的最好的一道题，之前在gethut上有一道原版的英文文档的题目，但是找不到。题目大概意思就是定义了一个ListNode，然后两个ListNode相加，返回一个ListNode。这里别人写过的一个编程过程，自己还没有好好推敲，等有时间，为大家写上注释和计算过程。

Definition for singly-linked list.

 public class ListNode {


int val;


ListNode next;


ListNode(int x) {


val = x;


next = null;


}
 
}

public class Solution {
 13
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
 14
ListNode head=null;
 15
if(l1==null&&l2==null) return head;
 16
head=new ListNode(l1.val+l2.val);
 17
ListNode tail=head;
 18
ListNode h1=l1.next;
 19
ListNode h2=l2.next;
 20
while(h1!=null&&h2!=null)
 21 
{
 22
ListNode n2=new ListNode(h1.val+h2.val);
 23
h1=h1.next;
 24
h2=h2.next;
 25
//insert into list 
 26
tail.next=n2;
 27
tail=tail.next;
 28
 29 
}
 30
// the leght is same
 31
if(h1!=null)
 32 
{
 33
while(h1!=null)
 34 
{
 35
tail.next=h1;
 36
tail=tail.next;
 37
h1=h1.next;
 38 
}
 39
 40
 41 
}
 42
if(h2!=null)
 43 
{
 44
while(h2!=null)
 45 
{
 46
tail.next=h2;
 47
tail=tail.next;
 48
h2=h2.next;
 49 
}
 50
 51
 52 
}
 53
//ceate a new Linklist
 54
 55
ListNode lhead=new ListNode(-10);
 56
tail=lhead;
 57
h1=head;
 58
int s=0;
 59
while(h1.next!=null) //utli the last poit
 60 
{
 61
if(h1.val+s>=10)
//is large than 10
 62 
{
 63
int t=h1.val+s;
 64
h1.val=t%10;
 65
s=t/10;
 66
 67 
}
 68
else
 69 
{
 70
h1.val=h1.val+s;
 71
s=0;
// I forget it ,so BEiJU
 72
 73 
}
 74
//insert into list
 75
tail.next=h1;
 76
tail=tail.next;
 77
 78
h1=h1.next;
 79
 80
 81
 82 
}
 83
if(h1.val+s>=10)
 84 
{
 85
int t2=h1.val+s;
 86
h1.val=t2%10;
 87
s=t2/10;
 88
tail.next=h1;
 89
tail=tail.next;
 90
 91
ListNode l4=new ListNode(s);
 92
tail.next=l4;
 93
tail=tail.next;
 94
 95 
}
 96
else
 97 
{
 98
h1.val=h1.val+s;
 99
tail.next=h1;
100
tail=tail.next;
101
102
103 
}
104
105
return lhead.next;
106
107
108 
}
109 }

编程者说之前的代码繁琐，没有很好的封装及重用，所以做了修改

/**
* Definition for singly-linked list.
* public class ListNode {
*
int val;
*
ListNode next;
*
ListNode(int x) {
*
val = x;
*
next = null;
*
}
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head=new ListNode(-1);
if(l1==null&&l2==null) return head.next;
ListNode tail=head;
int s=0;// jin wei
ListNode h1=l1;
ListNode h2=l2;
while(h1!=null&&h2!=null)
{
int t=h1.val+h2.val+s;
ListNode h3=h1.next;
h1.val=t%10;
s=t/10;
h1.next=null;
tail.next=h1;
tail=tail.next;
h1=h3;
h2=h2.next;
//insert into list
}
// the leght is same
ListNode h=(h1!=null)?h1:h2;
if(h!=null)
{
while(h!=null)
{
int t=h.val+s;
h.val=t%10;
s=t/10;
ListNode tem=h.next;
h.next=null;
tail.next=h;
tail=tail.next;
h=tem;
}
}
if(s>0)
{
ListNode n=new ListNode(s);
tail.next=n;
tail=tail.next;
}
return head.next;
}
}

最后

以上就是明理夏天最近收集整理的关于两个链表相加的全部内容，更多相关两个链表相加内容请搜索靠谱客的其他文章。