美文网首页
LeetCode - Add Two Numbers

LeetCode - Add Two Numbers

作者: 三生之二 | 来源:发表于2018-10-16 23:18 被阅读0次

    题目:
    /*
    给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。

    你可以假设除了数字 0 之外,这两个数字都不会以零开头。

    示例:

    输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出:7 -> 0 -> 8
    原因:342 + 465 = 807
    */

    解决方案如下:
    (以下代码包含了测试代码部分)

    struct ListNode {
        int val;
        ListNode *next;
        ListNode(int x) : val(x), next(nullptr) {}
    
        // 为了方便测试,加入该方法,将数字转换成node
        static ListNode *nodeWithNumber(int num) {
            if (num == 0)
            {
                return new ListNode(0);
            }
            int rest = num / 10;
            ListNode *head = new ListNode(num % 10);
            ListNode *tail = head;
            while (rest > 0)
            {
                ListNode *next = new ListNode(rest % 10);
                tail->next = next;
                tail = next;
                rest = rest / 10;
            }
            return head;
        }
    };
    
    class Solution {
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
            if (l1 == nullptr)
            {
                return l2;
            }
            if (l2 == nullptr)
            {
                return l1;
            }
    
            int sum = 0;
            ListNode *head = new ListNode(0);
            ListNode *cur = head;
    
            while (1)
            {
                if (l1 != nullptr)
                {
                    sum += l1->val;
                    l1 = l1->next;
                }
                if (l2 != nullptr)
                {
                    sum += l2->val;
                    l2 = l2->next;
                }
                cur->val = sum % 10;
                sum = sum / 10;
                if (l1 != nullptr || l2 != nullptr || sum)
                {
                    cur->next = new ListNode(0);
                    cur = cur->next;
                }
                else
                    break;
            }
    
            return head;
        }
    };
    
    void testNode();
    void printNode(ListNode *node, bool result);
    void printNode(ListNode *node);
    void testNormal();
    void testSpec();
    
    
    #include "iostream"
    int main() {
        
        testNode(); 
        testNormal();
        testSpec();
    
        system("pause");
    
        return 0;
    }
    
    void testNode(){
        ListNode *node1 = ListNode::nodeWithNumber(342);
        ListNode *node2 = ListNode::nodeWithNumber(0);
        printNode(node1);
        printNode(node2);
        printf("-----------------------------\n");
    
        free(node1);
        free(node2);
    }
    
    void testNormal() {
        ListNode *node1 = ListNode::nodeWithNumber(342);
        ListNode *node2 = ListNode::nodeWithNumber(465);
        printNode(node1);
        printNode(node2);
        ListNode *result1 = Solution().addTwoNumbers(node1, node2);
        printNode(result1, true);
        printf("-----------------------------\n");
    
        ListNode *node3 = ListNode::nodeWithNumber(32);
        ListNode *node4 = ListNode::nodeWithNumber(465);
        printNode(node3);
        printNode(node4);
        ListNode *result2 = Solution().addTwoNumbers(node3, node4);
        printNode(result2, true);
        printf("-----------------------------\n");
    
        free(node1);
        free(node2);
        free(node3);
        free(node4);
        free(result1);
        free(result2);
    }
    
    void testSpec() {
        ListNode *node1 = ListNode::nodeWithNumber(0);
        ListNode *node2 = ListNode::nodeWithNumber(465);
        printNode(node1);
        printNode(node2);
        ListNode *result1 = Solution().addTwoNumbers(node1, node2);
        printNode(result1, true);
        printf("-----------------------------\n");
    
        ListNode *node3 = ListNode::nodeWithNumber(342);
        ListNode *node4 = ListNode::nodeWithNumber(0);
        printNode(node3);
        printNode(node4);
        ListNode *result2 = Solution().addTwoNumbers(node3, node4);
        printNode(result2, true);
        printf("-----------------------------\n");
    
        ListNode *result3 = Solution().addTwoNumbers(nullptr, node4);
        printNode(result3, true);
        printf("-----------------------------\n");
    
        ListNode *result4 = Solution().addTwoNumbers(nullptr, nullptr);
        printNode(result4, true);
        printf("-----------------------------\n");
    
        free(node1);
        free(node2);
        free(node3);
        free(node4);
        free(result1);
        free(result2);
    // 因为这里result3得到的就是node4,所以不需要释放result3
    // result = nullptr
    }
    
    
    void printNode(ListNode *node) {
        printNode(node, false);
    }
    
    void printNode(ListNode *node, bool result) {
        if (node != nullptr)
        {
            ListNode *p = node;
            int num = 0;
            int i = 0;
            while (p != nullptr)
            {
                if (i == 0)
                {
                    num += p->val;
                }
                else
                {
                    num += p->val * (int)pow(10, i);
                }
                i++;
                printf("%d -> ", p->val);
                p = p->next;
            }
            
            printf("NULL <<<< %s == %d\n", result?"result":"num", num);
        }
        else
        {
            printf("node is a nullptr!\n");
        }
    }
    

    执行结果如下:

    2 -> 4 -> 3 -> NULL <<<< result == 342
    0 -> NULL <<<< result == 0
    -----------------------------
    2 -> 4 -> 3 -> NULL <<<< result == 342
    5 -> 6 -> 4 -> NULL <<<< result == 465
    7 -> 0 -> 8 -> NULL <<<< result == 807
    -----------------------------
    2 -> 3 -> NULL <<<< result == 32
    5 -> 6 -> 4 -> NULL <<<< result == 465
    7 -> 9 -> 4 -> NULL <<<< result == 497
    -----------------------------
    0 -> NULL <<<< result == 0
    5 -> 6 -> 4 -> NULL <<<< result == 465
    5 -> 6 -> 4 -> NULL <<<< result == 465
    -----------------------------
    2 -> 4 -> 3 -> NULL <<<< result == 342
    0 -> NULL <<<< result == 0
    2 -> 4 -> 3 -> NULL <<<< result == 342
    -----------------------------
    0 -> NULL <<<< result == 0
    -----------------------------
    node is a nullptr!
    -----------------------------
    请按任意键继续. . .
    

    相关文章

      网友评论

          本文标题:LeetCode - Add Two Numbers

          本文链接:https://www.haomeiwen.com/subject/xdwkzftx.html