题解 | #两个链表生成相加链表#（附带图解）

思路:

从题中给出的有效信息：

• 一个链表代表一个整数，返回多个链表的相加结果

故此顺位迭代就可以了，链表的问题大多借助栈和队列的结构思想

方法一：

具体做法：
申请两个栈空间和一个标记位，然后将两个栈中内容依次相加，将结果倒插入新节点中。

具体过程如下图所示：

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) {
        // write code here

        LinkedList<Integer> list1 = new LinkedList<>(); //list1栈
        LinkedList<Integer> list2 = new LinkedList<>(); //list2栈
        putData(list1, head1); //入栈
        putData(list2, head2);
        ListNode newNode = null;
        ListNode head = null;
        int carry = 0; //标记进位
        while(!list1.isEmpty() || ! list2.isEmpty() || carry != 0) {
            int x = (list1.isEmpty()) ? 0 : list1.pop();  //依次从栈中取出
            int y = (list2.isEmpty()) ? 0 : list2.pop();
            int sum = x + y + carry; //与进位一起相加
            carry = sum / 10; //更新进位
            //将计算值放入节点
            newNode = new ListNode(sum % 10);
                        //更新下一个节点的指向
            newNode.next = head;
            head = newNode;
        }
        return head;

    }
    private static void putData(LinkedList<Integer> s1,ListNode head1) {
        if (s1 == null) s1 = new LinkedList<>();
                //遍历节点将其插入栈中
        while(head1 != null) {
            s1.push(head1.val);
            head1 = head1.next;
        }
    }
}

复杂度分析：

• 时间复杂度：O(max(m,n))，由于只遍历了一次，只需要看两个链表更长的
• 空间复杂度：O(m+n)，申请了两个栈来记录元素

思路:

方法二：暴力搜索（不推荐，测试案例已超时）

具体做法：
将其转为字符串相加以后，然后构造链表；

具体过程如下图所示：

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) {
        // write code here
        StringBuilder num1 = new StringBuilder();
        StringBuilder num2 = new StringBuilder();
        //将链表用字符串拼接
        while (head1 != null) {
            num1.append(head1.val);
            head1 = head1.next;
        }
        while (head2 != null) {
            num2.append(head2.val);
            head2 = head2.next;
        }
        //将字符串用BigInteger转换进行计算
        java.math.BigInteger i = (new java.math.BigInteger(num1.toString())).add(new java.math.BigInteger(num2.toString()));
        String str = i + "";
        ListNode ans = new ListNode(-1);
        ListNode iter = ans;
        //最后转换为链表
        for (int j = 0; j < str.length(); j++) {
            iter.next = new ListNode(str.charAt(j) - '0');
            iter = iter.next;
        }
        return ans.next;
    }

}

复杂度分析：

• 时间复杂度：O(m+n) ,需要遍历两次，然后相加
• 空间复杂度：O(m+n) ,创建了多个n+m个节点空间