【牛客】链表相加(2)
浏览 485 | 评论 0 | 字数 1619
TTQ
2022年04月21日
  • 原题链接: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 授权协议,转载请注明来源,谢谢!
    评论
    与本文无关评论请发留言板。请不要水评论,谢谢。
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论