题目主要信息:

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

具体思路:

既然链表每个节点表示数字的每一位,那相加的时候自然可以按照加法法则,从后往前依次相加。但是,链表是没有办法逆序访问的,这是我们要面对第一只拦路虎。解决它也很简单,既然从后往前不行,那从前往后总是可行的吧,将两个链表反转一下,即可得到个十百千……各个数字从前往后的排列,相加结果也是个位在前,怎么办?再次反转,结果不就正常了。

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

alt

代码实现:

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; //断开链表,要记录后续一个
            cur->next = pre; //当前的next指向前一个
            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); //结果反转回来
    }
};

复杂度分析:

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