LeetCode 2. Add Two Numbers题目解析-wowAC

Description

You are given two non-empty linked lists representing two non-negative integers. 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.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.


题目复述

    给你两个非空的链表,链表中存储着两个非负数,数字在连表里面倒序存储(即链表头部存储个位,依次类推)且链表的每个节点包含一个数字,你的任务是将两个数字的和的结果返回,结果存储在链表中。

    假定链表中的两个数不包含前导0,除非这个数是0。ps:题目给定的链表和结果链表都是无头链表。

题目解析

1.模拟法

    此题需要模拟算数加法,因为都是非负整数的加法,所以只需要用一个变量c来记录低位给高位贡献的进位即可。需要注意的是,两个n为数相加结果可能是n+1位数,因此需要在最后判断c,如果不是0,则需要开辟新空间存储。在实现的时候为了简单,可以给结果链表加一个头节点处理。

/**
 * 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 *head = new ListNode(0);
        ListNode *mv = head;
        int c = 0;       //进位
        while(l1!=NULL && l2!=NULL) {
            int bit = l1->val + l2->val + c;
            ListNode *temp = new ListNode(bit%10);
            c = bit / 10;
            mv->next = temp;
            mv = mv->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        while(l1 != NULL) {
            int bit = l1->val + c;
            ListNode *temp = new ListNode(bit % 10);
            c = bit / 10;
            mv->next = temp;
            mv = mv->next;
            l1 = l1->next;
        }
        while(l2 != NULL) {
            int bit = l2->val + c;
            ListNode *temp = new ListNode(bit % 10);
            c = bit / 10;
            mv->next = temp;
            mv = mv->next;
            l2 = l2->next;
        }
        if(c != 0) {        //不能忘记
            ListNode *temp = new ListNode(c);
            mv->next = temp;
        }
        return head->next;
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注