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

题目主要信息:

• 给定两个链表，每个链表中节点值都是0-9，每个链表就可以表示一个数字
• 将两个链表表示的数字相加，结果也存在链表中

举一反三：

学习完本题的思路你可以解决如下题目：

BM1.反转链表

BM86.大数加法

方法：反转链表法（推荐使用）

思路：

既然链表每个节点表示数字的每一位，那相加的时候自然可以按照加法法则，从后往前依次相加。但是，链表是没有办法逆序访问的，这是我们要面对第一只拦路虎。解决它也很简单，既然从后往前不行，那从前往后总是可行的吧，将两个链表反转一 下：

while(cur != null){
    //断开链表，要记录后续一个
    ListNode temp = cur.next;
    //当前的next指向前一个
    cur.next = pre; 
    //前一个更新为当前
    pre = cur; 
    //当前更新为刚刚记录的后一个
    cur = temp; 
}

即可得到个十百千……各个数字从前往后的排列，相加结果也是个位在前，怎么办？再次反转，结果不就正常了。

具体做法：

• step 1：任意一个链表为空，返回另一个链表就行了，因为链表为空相当于0，0加任何数为0，包括另一个加数为0的情况。
• step 2：相继反转两个待相加的链表，反转过程可以参考反转链表。
• step 3：设置返回链表的链表头，设置进位carry=0.
• step 4：从头开始遍历两个链表，直到两个链表节点都为空且carry也不为1. 每次取出不为空的链表节点值，为空就设置为0，将两个数字与carry相加，然后查看是否进位，将进位后的结果（对10取模）加入新的链表节点，连接在返回链表后面，并继续往后遍历。
• step 5：返回前将结果链表再反转回来。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    //反转链表
    public ListNode ReverseList(ListNode pHead) { 
        if(pHead == null)
            return null;
        ListNode cur = pHead;
        ListNode pre = null;
        while(cur != null){
            //断开链表，要记录后续一个
            ListNode temp = cur.next;
            //当前的next指向前一个
            cur.next = pre; 
            //前一个更新为当前
            pre = cur; 
            //当前更新为刚刚记录的后一个
            cur = temp; 
        }
        return pre;
    }
    
    public ListNode addInList (ListNode head1, ListNode head2) {
        //任意一个链表为空，返回另一个
        if(head1 == null) 
            return head2;
        if(head2 == null)
            return head1;
        //反转两个链表
        head1 = ReverseList(head1); 
        head2 = ReverseList(head2);
        //添加表头
        ListNode res = new ListNode(-1); 
        ListNode head = res;
        //进位符号
        int carry = 0; 
        //只要某个链表还有或者进位还有
        while(head1 != null || head2 != null || carry != 0){ 
            //链表不为空则取其值
            int val1 = head1 == null ? 0 : head1.val; 
            int val2 = head2 == null ? 0 : head2.val;
            //相加
            int temp = val1 + val2 + carry; 
            //获取进位
            carry = temp / 10; 
            temp %= 10; 
            //添加元素
            head.next = new ListNode(temp); 
            head = head.next;
            //移动下一个
            if(head1 != null) 
                head1 = head1.next;
            if(head2 != null)
                head2 = head2.next;
        }
        //结果反转回来
        return ReverseList(res.next); 
    }
}

C++实现代码：

class Solution {
public:
    //反转链表
    ListNode* ReverseList(ListNode* pHead) { 
        if(pHead == NULL)
            return NULL;
        ListNode* cur = pHead;
        ListNode* pre = NULL;
        while(cur != NULL){
            //断开链表，要记录后续一个
            ListNode* temp = cur->next; 
            //当前的next指向前一个
            cur->next = pre; 
            //前一个更新为当前
            pre = cur; 
            //当前更新为刚刚记录的后一个
            cur = temp; 
        }
        return pre;
    }
    
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        //任意一个链表为空，返回另一个
        if(head1 == NULL) 
            return head2;
        if(head2 == NULL)
            return head1;
        //反转两个链表
        head1 = ReverseList(head1); 
        head2 = ReverseList(head2);
        //添加表头
        ListNode* res = new ListNode(-1); 
        ListNode* head = res;
        //进位符号
        int carry = 0; 
        //只要某个链表还有或者进位还有
        while(head1 != NULL || head2 != NULL || carry != 0){ 
            //链表不为空则取其值
            int val1 = head1 == NULL ? 0 : head1->val; 
            int val2 = head2 == NULL ? 0 : head2->val;
            //相加
            int temp = val1 + val2 + carry; 
            //获取进位
            carry = temp / 10; 
            temp %= 10; 
            //添加元素
            head->next = new ListNode(temp); 
            head = head->next;
            //移动下一个
            if(head1 != NULL) 
                head1 = head1->next;
            if(head2 != NULL)
                head2 = head2->next;
        }
        //结果反转回来
        return ReverseList(res->next); 
    }
};

Python代码实现：

class Solution:
    #反转链表
    def ReverseList(self, pHead:ListNode): 
        if pHead == None:
            return None
        cur = pHead
        pre = None
        while cur:
            #断开链表，要记录后续一个
            temp = cur.next 
            #当前的next指向前一个
            cur.next = pre 
            #前一个更新为当前
            pre = cur 
            #当前更新为刚刚记录的后一个
            cur = temp 
        return pre
    
    def addInList(self , head1: ListNode, head2: ListNode) -> ListNode:
        #任意一个链表为空，返回另一个
        if head1 == None: 
            return head2
        if head2 == None:
            return head1
        #反转两个链表
        head1 = self.ReverseList(head1) 
        head2 = self.ReverseList(head2)
        #添加表头
        res = ListNode(-1) 
        head = res
        #进位符号
        carry = 0 
        #只要某个链表还有或者进位还有
        while head1 != None or head2 != None or carry != 0: 
            #链表不为空则取其值
            val1 = 0 if head1 == None else head1.val 
            val2 = 0 if head2 == None else head2.val
            #相加
            temp = val1 + val2 + carry 
            #获取进位
            carry = (int)(temp / 10) 
            temp %= 10
            #添加元素
            head.next = ListNode(temp) 
            head = head.next
            #移动下一个
            if head1: 
                head1 = head1.next
            if head2:
                head2 = head2.next
        #结果反转回来
        return self.ReverseList(res.next) 

复杂度分析：

• 时间复杂度：$O(max(m,n))O(max(m,n))$，其中$mm$与$nn$分别为两个链表的长度，翻转链表三次，复杂度分别是$O(n)O(n)$、$O(m)O(m)$、$O(max(m,n))O(max(m,n))$，相加过程也是遍历较长的链表
• 空间复杂度：$O(1)O(1)$，常数级指针，没有额外辅助空间，返回的新链表属于必要空间