面试题 02.05. 链表求和

利刃大大

发布于 2023-04-12 14:08:38

1500

发布于 2023-04-12 14:08:38

文章被收录于专栏：编程语言/linux/算法

面试题 02.05. 链表求和

难度中等140

给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

示例：

输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912

**进阶：**思考一下，假设这些数位是正向存放的，又该如何解决呢?

示例：

输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912

思路：

这道题与数组求和以及字符串求和类似，都是用每一位相加还有加上进位求得结果赋给一个新的链表 tmp，直到两个链表都遍历完。但记得最后判断是否还有多的一个进位需要加上。

题目中还提到如果是正向存放的话，那可以先用将两个链表的值放到两个栈中，然后就像原来是思路一样，只不过变成了从栈中取数值而已！

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //创建一个头节点
        ListNode* newhead = new ListNode(-1);
        //创建一个新链表用于存储每个位的和
        ListNode* tmp = new ListNode(0);
        newhead->next = tmp;

        int next = 0; //表示进位
        while(l1 != nullptr || l2 != nullptr)
        {
            int n1 = 0;
            if(l1 != nullptr)
            {
                n1 = l1->val;
                l1 = l1->next;
            }

            int n2 = 0;
            if(l2 != nullptr)
            {
                n2 = l2->val;
                l2 = l2->next;
            }

            int sum = n1 + n2 + next;
            if(sum > 9) //判断是否需要进位 
            {
                sum -= 10;
                next = 1;
            }
            else
            {
                next = 0;
            }

            tmp->val = sum;
            if(l1 != nullptr || l2 != nullptr)
            {
                ListNode* tmp1 = new ListNode(0);
                tmp->next = tmp1;
                tmp = tmp1;
            }
        }
        if(next == 1)
        {
            ListNode* tmp1 = new ListNode(0);
            tmp->next = tmp1;
            tmp1->val = 1;
        }

        //将头节点释放
        ListNode* t = newhead->next;
        delete newhead;
        return t;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-07-24，如有侵权请联系 cloudcommunity@tencent.com 删除

遍历