Not Only Algorithm,不仅仅是算法,关注数学、算法、数据结构、程序员笔试面试以及一切涉及计算机编程之美的内容 。。
你的位置:NoAlGo博客 » 题解 » 

Leetcode Add Two Numbers

Leetcode algorithms 第 2 题: Add Two Numbers。

题目

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 dummy(-1), *p = &dummy; //标记用的头结点
        
        int carry = 0; //进位
        while (l1 != NULL && l2 != NULL)
        {
            int t = l1->val + l2->val + carry;
            if (t >= 10) t -= 10, carry = 1;
            else carry = 0;
            p->next = new ListNode(t);
            p = p->next, l1 = l1->next, l2 = l2->next;
        }
        
        while (l1 != NULL) //l1较长
        {
            int t = l1->val + carry;
            if (t >= 10) t -= 10, carry = 1;
            else carry = 0;
            p->next = new ListNode(t);
            p = p->next, l1 = l1->next;
        }
        while (l2 != NULL) //l2较长
        {
            int t = l2->val + carry;
            if (t >= 10) t -= 10, carry = 1;
            else carry = 0;
            p->next = new ListNode(t);
            p = p->next, l2 = l2->next;
        }
        
        if (carry) //还有进位
            p->next = new ListNode(1);
            
        return dummy.next;
    }
};
上一篇: 下一篇:

我的博客

NoAlGo头像编程这件小事牵扯到太多的知识,很容易知其然而不知其所以然,但真正了不起的程序员对自己程序的每一个字节都了如指掌,要立足基础理论,努力提升自我的专业修养。

站内搜索

最新评论