首页 > 代码库 > LeetCode-004 Add Two Numbers

LeetCode-004 Add Two Numbers

2024-07-04 10:30:52   222人阅读

【题目】

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8


【题意】

题意是给定两个链表，每个链表表示一个十进制数，链表中每个结点表示数中每一位的值，每个数倒序呈现（个位->十位->百位->...），将这两个链表相加，然后返回相加后的链表


【思路】

    依次对应位相加，注意保存进位值


【代码】

/**
 * 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*p1=l1;                 //l1的扫描指针
        ListNode*p2=l2;                 //l2的扫描指针
        ListNode*p=NULL, *head=NULL;    //新链表的扫描指针和头指针
        int toNext=0;   //记录进位值
        while(p1&&p2){
            int sum=p1->val+p2->val+toNext;
            toNext=sum/10;      //更新toNext
            ListNode* digit=new ListNode(sum%10);   //计算当前位值并创建结点
            if(p!=NULL)p->next=digit; //将当前结点添加到新链表中【不能使用!p】
            else head=digit;
            p=digit;
            p1=p1->next;
            p2=p2->next;
        }
        while(p1){
            int sum=p1->val+toNext;
            toNext=sum/10;      //更新toNext
            ListNode* digit=new ListNode(sum%10);   //计算当前位值并创建结点
            if(p!=NULL)p->next=digit; //将当前结点添加到新链表中【不能使用!p】
            else head=digit;
            p=digit;
            p1=p1->next;
        }
        while(p2){
            int sum=p2->val+toNext;
            toNext=sum/10;      //更新toNext
            ListNode* digit=new ListNode(sum%10);   //计算当前位值并创建结点
            if(p!=NULL)p->next=digit; //将当前结点添加到新链表中【不能使用!p】
            else head=digit;
            p=digit;
            p2=p2->next;
        }
        //别忘了最后是否有进位值
        if(toNext!=0){
            ListNode* digit=new ListNode(toNext);   //计算当前位值并创建结点
            p->next=digit; //将当前结点添加到新链表中
        }
        return head;
    }
};


联系
我们