java单链表加法_java链表及实现leetcode题

package leetcode;

public class AddTwoNumbers {

/**

* 两个链表相加

* input: (2 -> 4 -> 3) +(5->6->4)

* output: 7->0->8

* 2+5=7 4+6=10(但要显示0) 进一位 1+3+4 =8

* time:O(n)

* space:O(n)

* @param args

*/

public static void main(String[] args) {

// TODO Auto-generated method stub

//try

ListNode l1 = new ListNode(2);

ListNode l12 = new ListNode(4);

ListNode l13 = new ListNode(3);

l1.next = l12;

l12.next = l13;

ListNode l2 = new ListNode(5);

ListNode l22 = new ListNode(6);

ListNode l23 = new ListNode(4);

l2.next = l22;

l22.next = l23;

ListNode result = new AddTwoNumbers().addTwoNumbers(l1, l2);

result.printList();

}

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode dummy = new ListNode(0);

int sum = 0;

ListNode cur = dummy;

ListNode p1= l1,p2=l2;

//让p1和p2作为临时变量存储链表的各个值进行相加

//若是 链表的next有值，即next指向下一个元素，则继续做加法

while(p1!=null || p2!=null) {

if(p1!=null) {

sum+=p1.val;

p1=p1.next;

}

if(p2!=null) {

sum+=p2.val;

p2=p2.next;

}

//10取余数

cur.next = new ListNode(sum % 10);

//如果相加大于10，则后位加1

sum=sum/10;

//游标下移，并且带上上一位的进位

cur = cur.next;

}

if(sum == 1) {

cur.next = new ListNode(1);

}

//最后返回的是 next是因为 链表的第一个值是0

return dummy.next;

}

}

/**

* 自定义链表类,每个对象都有自己的next对象

* @author mac

*

*/

class ListNode {

int val;

ListNode next;

public ListNode(int x) {

val = x;

}

public void printList(){

ListNode tmp=this;

//遍历输出 next的val

while(tmp!=null){

System.out.print(tmp.val);

if(tmp.next!=null) {

System.out.print("->");

}

tmp=tmp.next;

}

System.out.println();

}

}