两个链表生成相加的链表

1.题目描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

2.题目分析

• 本题的顺序与链表相加的顺序是相反的是本题的一个难点
• 可以借助栈来存储链表的数
• 依次把所有数字压入栈中，再依次取出相加。计算过程中需要进位的情况。
• 注意处理前置0的情况,比如链表的长度不一样就需要加上前置0，比如937和63.做加法处理的时候就可以用栈的非空判断。

3.源代码

 import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
       ListNode  dummyHead=new ListNode(-1);
                   ListNode  cur=dummyHead;
                   int  carry=0;
                   Stack<Integer>  stack1=new  Stack();
                   Stack<Integer>  stack2=new  Stack();
                     while(head1!=null){
                         stack1.push(head1.val);
                          head1=head1.next;
                     }
                   while(head2!=null){
                         stack2.push(head2.val);
                          head2=head2.next;
                     }
          while(!stack1.isEmpty()||!stack2.isEmpty()||carry!=0){
                           int  x=stack1.isEmpty()?0:stack1.pop();
                           int  y=stack2.isEmpty()?0:stack2.pop();
                           int  sum=x+y+carry;
                           carry=sum/10;
                           sum=sum%10;
                           cur.next=new ListNode(sum);
                           cur=cur.next;           
          }

        return   reverse(dummyHead.next);
    }
    ListNode  reverse(ListNode head){
          ListNode pre,cur,next;
          pre=null;
          cur=next=head;
        while(cur!=null){
              next=cur.next;
              cur.next=pre;
            pre=cur;
            cur=next;
        }
          return  pre;
    }
}

复杂度分析

• 时间复杂度：O(max(m,n)),其中m和n分别为两个链表的长度。我们需要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。
• 空间复杂度：O(m+n),其中 m 和 n 分别为两个链表的长度。空间复杂度主要取决于我们把链表内容放入栈中所用的空间。