首页 > 代码库 > 就是两个链表中的数相加

就是两个链表中的数相加

  想起那夕阳下的奔跑,那是我逝去的青春   ----万万没想到

我一看到,就觉得很简单,因为就是那个大数相加的思想啊,后来才知道各种情况,调了2个多小时,坑爹,不过leecode测试用例非常好。

1.链表合并,跟那个有序链表合并为一个类似,

2.合并之后,利用大数相加,超过十进位,最后一个节点要特殊处理,我写了这么长代码,大量重复的代码。所以仔细思考了下,重构了代码;

链表合并的时候直接就能相加啊,遍历一遍就Ok了,前后两次代码,这里面有个小技巧,如果头结点容易改变,就自己建立头结点,然后去掉就行,

在解决链表问题很常用,

 

方法一: AC  冗余高

  1 /**  2  * Definition for singly-linked list.  3  * public class ListNode {  4  *     int val;  5  *     ListNode next;  6  *     ListNode(int x) {  7  *         val = x;  8  *         next = null;  9  *     } 10  * } 11  */ 12 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 }

2.又调了1个小时,简明多了,当你大量写重复代码,表明你写的代码有问题。

 1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {14         ListNode head=new ListNode(-1);15         if(l1==null&&l2==null) return head.next;16         ListNode tail=head;17         int s=0;// jin wei 18 19         ListNode h1=l1;20         ListNode h2=l2;21         while(h1!=null&&h2!=null)22         {23             int t=h1.val+h2.val+s;24             ListNode h3=h1.next;25                 h1.val=t%10;26                 s=t/10;27             h1.next=null;28             tail.next=h1;29             tail=tail.next;30             h1=h3;31             h2=h2.next;32             //insert into list 33         }34        35         // the leght is same36         ListNode h=(h1!=null)?h1:h2;37         38         if(h!=null)39         {40             while(h!=null)41             {42                 int t=h.val+s;43                 h.val=t%10;44                 s=t/10;45                 ListNode tem=h.next;46                 h.next=null;47                 48                 tail.next=h;49                 50                 tail=tail.next;51                 h=tem;52             }53             54             55         }56        57             if(s>0)58             {59                 ListNode n=new ListNode(s);60                 tail.next=n;61                 tail=tail.next;62             }63     64         return head.next;65         66     }67 }