题解 | #链表相加(二)#

思路分析：

思路一：

本题的链表相加本质上其实是两数相加，我第一反应就是读取两个链表凑成俩整数，然后数学计算求和，再依次取和数的个位来创建链表节点，最后通过头插法来保证结果的正常排序。但这里的节点个数范围在百万级，在java中哪怕用long也不够表示一百万位数，但测试小规模数据时完全没问题，Python语言可以直接采用这种思路。

思路二：

考虑到数学运算，而链表不支持索引，所以想到翻转链表，这样可以得到按（个十百千...）顺序排列的链表，这样我们就可以直接遍历链表来完成运算。每次访问的节点都是当前还未完成运算的节点中的最低位，至于两个链表的长度问题完全不用考虑，因为当某个链表遍历到null时直接取val=0就可以了。这里主要是注意进位，采用一个变量flag来作为进位标志，每一次的加法运算要将进位考虑进去，最后根据加法运算结果创建节点。由于是从最低位开始运算并创建链表节点的，所以需要弄成头插法，以保证最终结果链表的顺序是按（万千百十个...）进制正序。

Java代码实现：

public class Solution {
    public ListNode addInList (ListNode head1, ListNode head2) {
        if(head1 == null)   return head2;
        if(head2 == null)   return head1;
        //倒转链表，使其节点排列是按个十百...的顺序，方便运算
        head1 = reverse(head1);
        head2 = reverse(head2);
        ListNode phead = new ListNode(0);   //创建虚拟头指针便于头插法创建链表
        int flag = 0;   //进位
        while(head1 != null || head2!=null || flag!=0){
            int value1 = head1!=null ? head1.val : 0;
            int value2 = head2!=null ? head2.val : 0;
            int value = (value1 + value2 +flag)%10;
            // 由于结果是按进制正序的，所以采用头插法
            ListNode node = new ListNode(value);
            node.next = phead.next;
            phead.next = node;
            flag = (value1 + value2 +flag)/10;
            if(head1!=null)     head1 = head1.next;
            if(head2!=null)     head2 = head2.next;
        }
        return phead.next;
    }
    public ListNode reverse(ListNode node){
        if(node == null) return null;
        ListNode cur = node;
        ListNode pre = null;
        while(cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

复杂度分析：

时间：O(n) 空间：O(n)