题解 | #【冲刺双百】链表相加(二)#

一道思路大家都懂的麻烦题

思路

1. 将两个列表反转
2. 对应位相加，再加上上一位的进位值，计算当前位的值与进位
3. 根据链表长度分类讨论（我在这里遍历时覆盖了head1链表）
   • 两链表长度相同：遍历结束时判断进位是否为0，若不为0则生成新结点接在链表后面
   • 链表1长度大于链表2：链表2遍历结束时，继续遍历链表1，计算公式为链表1结点值+进位值；链表1遍历结束时根据进位是否为0决定是否需要生成新结点。
   • 链表1长度小于链表2：链表1遍历结束时，令链表1最后一个结点指向此时链表2下一个结点，计算公式为链表2结点值+进位值；链表2遍历结束时根据进位是否为0决定是否需要生成新结点。
4. 反转链表1得到结果

优化

不难发现，链表长度不相同时，后半部分的计算逻辑基本相同。这里我们将链表1作为最后答案，故链表2长度更大时，我们将和链表1与链表2的后半部分连接起来，与链表1长度更大时的处理就如出一辙了。

复杂度分析

时间复杂度：反转链表共3次+遍历链表1次->k*O(n)->O(n)
空间复杂度：设长链表长度为n；复杂度最大为O(n+1)

代码

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public static ListNode ReverseList(ListNode head) {
        if(head==null) return head;
        ListNode nex=head.next;
        ListNode las=null;
        head.next=las;
        while(nex!=null){
            las=head;
            head=nex;
            nex=head.next;
            head.next=las;
        }
        return head;
    }
    
    public ListNode addInList (ListNode head1, ListNode head2) {
        head1=ReverseList(head1);
        head2=ReverseList(head2);
        ListNode h1=head1;
        ListNode h2=head2;
        int c=0;//进位
        int tmp=0;//存储中间计算结果
        ListNode las=head1;//head1的上一个结点
        while(head1!=null&&head2!=null){
            tmp=head1.val+head2.val+c;//计算当前位的结果
            head1.val=tmp%10;
            c=tmp/10;//计算进位
            las=head1;
            //继续向下遍历
            head1=head1.next;
            head2=head2.next;
        }
        //head1为长链表，head2为短链
        if(head1==null){
            las.next=head2;
            head1=head2;
        }
            //当head1也为空时说明计算结束
            while(head1!=null){
                tmp=head1.val+c;
                head1.val=tmp%10;
                c=tmp/10;
                las=head1;
                head1=head1.next;
            }
            //如果最后一位无进位
            if(c==0){
                return ReverseList(h1);
            }
            //如果最后一位有进位
            else{
                ListNode h=new ListNode(c);
                las.next=h;
            }
            return ReverseList(h1);
    }
}