原题链接：https://www.nowcoder.com/practice/c56f6c70fb3f4849bc56e33ff2a50b6b

题目描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。 给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围：0 \le n,m \le 10000000≤n,m≤1000000，链表任意值 0 \le val \le 90≤val≤9
要求：空间复杂度 O(n)O(n)，时间复杂度 O(n)O(n)

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

一开始没看到数据要求，试着用转成数字直接相加，结果当然是不对的，因为题目给的位数非常大，因此必须一位一位的处理。

我选择了先将两个链表反转再进行相加，要记得处理进位的情况即可。

class Solution {
  public:
      // 反转链表
    ListNode* reverse(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* cur = head;

        while (cur) {
            ListNode* next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
    /**
     *
     * @param head1 ListNode类
     * @param head2 ListNode类
     * @return ListNode类
     */
    ListNode* addInList(ListNode* head1, ListNode* head2) {
        // write code here
        head1 = reverse(head1);
        head2 = reverse(head2);

        ListNode* cur = new ListNode(-1);
        ListNode* pre = nullptr;
        bool ex = false;// 标记进位
        while (head1 || head2) {
            int sum = 0;
            if (head1) {
                sum += head1->val;
                head1 = head1->next;
            }
            if (head2) {
                sum += head2->val;
                head2 = head2->next;
            }
            cur = new ListNode((sum + ex) % 10);
            cur->next = pre;
            pre = cur;
            ex = (sum + ex) / 10;
        }
        return cur;
    }
};

本文作者：TTQ
本文链接：https://blog.ponder.fun/archives/141.html
最后修改时间：2022-04-21 22:03:46
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！