简单的两数之和再次乱入<< Add Two Numbers >>

时间：2021-11-09 04:53:37
请看题目描述：


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




//Definition for singly-linked list.


     class ListNode

     {

         public int val;

         public ListNode next;

         public ListNode(int x)

         {

             val = x;

         }



10  } 








 分析：
　　这个两数相加不难，只是两个正整数都放在了链表里面了而已。还有一点是，整数的每一位数字都是放过来存放的，那么这样就明显降低了难度了，实现起来就像我们小学的时候列树式计算两个数的和，从低位加起，和与10的余数放在本位，和与10的商产生高位进位。在本题只需从两个链表的表头开始相加，用一个存放计算结果的链表的对应位置存放两个链表对应位置的整数和进位和除以10的余数，并用临时变量存放进位，用于加入下一次的两个整数之和中。直到两个链表中长的链表也遍历完了，那么结果链表也就出来了。结果链表的整数的各位数字也是反序的。

　　从前面的分析来看我们可以使用递归和非递归两种算法实现。
　　C#参考实现如下：　　






 递归实现：




        public ListNode AddTwoNumbers(ListNode l1, ListNode l2)

    {

             return AddTwoNumbers(l1, l2, );

    }

        public ListNode AddTwoNumbers(ListNode l1, ListNode l2 , int carry)

    {

              if(l1 == null && l2 == null && carry ==)

       {

                  return null;

       }

              ListNode result = new ListNode();

              int sum = (l1 == null ?  : l1.val) + (l2 == null ?  : l2.val) + carry;

              result.val = sum % ;

              ListNode more = AddTwoNumbers( l1 == null ? null : l1.next ,

                                                                      l2 == null ? null :l2.next,

                                                                       sum >=  ?  :   );

              result.next = more;

              return result;

         }




　






非递归实现：




  public ListNode AddTwoNumbers2(ListNode l1, ListNode l2)

 {

              ListNode node = new ListNode();

              ListNode result = node;

              int carry = ;

              while(l1 != null || l2 != null || carry != )

       {

                  int  sum =( l1 ==null ?  : l1.val )+( l2 == null ?  : l2.val )+ carry;

                  l1 =( l1 ==null ? null : l1.next);

                  l2 =( l2 == null ? null : l2.next);

                 node.next = new ListNode(sum %  );

                 node = node.next;

                  carry = sum / ;

        }

              return result.next;

  }




　






 总结：这个题目不难只要静下心来就可以想出来，涉及的细节问题也不多。那么如果把题目改一下，改成两个链表中存放正整数的每一位数字是正向存放的，又该如何实现呢？注意：链表是单向的。这时就要注意两个整数的位数长短了。我们可以这样实现：a）先比较两个链表的长度并用零填充较短的链表  b）递归结果加到首部
　　




　　　　　　　　　　　　　　　　　　　　　　　　　　　　
相关文章