C/C++教程

LeetCode编程每日一题(C++)——链表实现两数相加

本文主要是介绍LeetCode编程每日一题(C++)——链表实现两数相加,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

在这里插入图片描述
示例1:
在这里插入图片描述

在这里插入图片描述
方法一:
将两个链表中较短的一个进行补零,之后对应相加

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        // 为了实现链表的(逆向)两数相加,首先需要统一数据格式,即将两链表位数补齐;
        // 而要想补齐位数,需要首先统计链表的各自长度
        int len1 = 1;
        int len2 = 1;//记录链表长度
        ListNode* p = l1;
        ListNode* q = l2;//链表的移动指针
        //首先计算链表的长度
        while (p->next != NULL){
            len1 ++;
            p = p->next;
        }
        while (q->next != NULL){
            len2 ++;
            q = q->next;
        }
        //为较短的一个链表补零
        if (len1 >len2){//为l2补零
            for (int i=0; i<len1-len2; i++){
                q->next = new ListNode(0);
                q = q->next;
            }
        }
        else{//为l1补零
            for (int i=0; i<len2-len1; i++){
                p->next = new ListNode(0);
                p = p->next;
            }
        }
        //将两数相加
        p = l1;
        q = l2;
        ListNode* l3 = new ListNode(-1);
        ListNode* w = l3;
        bool flag = false;//是否进位
        int sum;
        for (int i=0; i<len1 || i<len2; i++){//两链表长度相同,从低到高遍历每一个数码进行相加,考虑进位问题
            sum = flag + p->val + q->val;
            flag = sum>9?true:false;
            w->next = new ListNode(sum%10);
            w = w->next;
            p = p->next;
            q = q->next;
        }
        if (flag){//若最高位仍进行进位
            w->next = new ListNode(1);
        }
        l3 = l3->next;
        return l3;
    }
};

方法二:
不进行对齐补零

// Solution 2: 
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head = new ListNode(-1);//待输出链表
        ListNode* h = head;//可移动的指针
        int sum;//存储相加结果
        bool flag = false;//是否进位的标志
        while(l1!=NULL || l2!=NULL){
            sum = 0 + flag;//每次使用时归零处理,同时考虑来自上一位的进位
            if(l1 != NULL){
                sum += l1->val;
                l1 = l1->next;
            }
            if (l2 != NULL){
                sum += l2->val;
                l2 = l2->next;
            }

            h->next = new ListNode(sum%10);
            h = h->next;
            flag = sum>9?true:false;
        }
        if (flag){
            h->next = new ListNode(1);
        }
        head = head->next;
        return head;
    }
};

注:以上代码为本人根据网友高赞题解编写,略有改动,并非原创

这篇关于LeetCode编程每日一题(C++)——链表实现两数相加的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!