coding

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8

簡單來說，給兩個單向鏈表，元素反向相加并以同樣規(guī)則進(jìn)行儲存。注意進(jìn)位！

以下是我寫的java程序：

一、常規(guī)做法：

逐一抽取計(jì)算，并考慮其中某個到達(dá)鏈尾的情況。

/**
* Definition for singly-linked list. 
* public class ListNode {
* int val;
 * ListNode next;
 * ListNode(in x) { val = x; } 
*  }
 */
public class Solution { 
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode slist = new ListNode(0); 
    ListNode clist = slist;
    ListNode nlist = new ListNode(0); 
    //int sval = 0;
    int flag = 0; // 進(jìn)位 
    //1. if First Node of l1 or l2 is null       
    if(l1==null||l2==null){
       return (l1==null)?((l2==null)?(slist):(l2)):(l1);
    }

    //2.1 當(dāng)l1，l2都非鏈尾時(shí)，loop 
    while(true)
    {
      clist.val = (l1.val + l2.val + flag)%(10);
      flag = (l1.val + l2.val + flag)/10; 
      //next node 
      l1 = l1.next;
      l2 = l2.next;
      //2.1.1 若任意一個為鏈尾，則跳出             
      if(l1==null||l2==null){
            break;
       }else{ 
        clist.next= new ListNode(0);
        clist =clist.next; } };//while 
       //2.2 如果兩個同時(shí)為鏈尾時(shí)              
       if(l1==null&&l2==null) 
       {
           //2.2.1 若兩個為鏈尾且有進(jìn)位，結(jié)果需進(jìn)位 
          if(flag==1){ 
             nlist = new ListNode(flag); 
             clist.next = nlist;
           }else{ 
            return slist; 
             }
      }else //2.2 一個到達(dá)鏈尾、一個還未 
      {
         ListNode onelist = new ListNode(0);
         if(l1==null) 
         {onelist = l2;
          }else
         {onelist = l1; }
          while(onelist!= null)
        { 
         clist.next = new ListNode(0);
         clist = clist.next; 
         clist.val = (onelist.val + flag)%10;
         flag = (onelist.val + flag)/10;
         onelist = onelist.next; 
     } //2.2.1 當(dāng)另外一個也到達(dá)鏈尾，判斷是否有進(jìn)位      
      if(flag==1)
      {
          clist.next = new ListNode(flag);
       }
  } 
  return slist;
 }
}

二、思路清晰的做法：

將鏈表先讀取為數(shù)值類型，相加后再將結(jié)果轉(zhuǎn)為規(guī)定鏈表。該方法思路十分清晰簡單，但是要逐一是否會溢出，時(shí)間及空間復(fù)雜度增加等問題。

三、更優(yōu)方案：

此處有更好更簡潔的解決方案供參考：：Leetcode – Add Two Numbers (Java)。該方法分別判斷兩個鏈表是否到鏈尾了。就不需要像一那樣考慮多種情況，似乎很多問題都可以有將各種情況統(tǒng)一的方式。下次做之前要多思考是否有這種方式。