黑马程序员技术交流社区

标题: LeetCode 算法题 2. Add Two Numbers [打印本页]

---

作者: Miss_Allsunday    时间: 2017-6-14 11:11
标题: LeetCode 算法题 2. Add Two Numbers

2. Add Two Numbers

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.

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

你得到两个非空的链表，这两个链表代表两个非负的整数。这些数字是以反序存储的并且每一个node只用来存储一个数字。请将这两个数相加并且以单链表的形式返回。

举例：

输入: (2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 0 -> 8

（2 -> 4 -> 3)可以看成342， (5 -> 6 -> 4)可以看成465，相加获得(7 -> 0 -> 8)可以看成807.

/**

* 定义的单链表结构体

* struct ListNode {

*     int val;

*     struct ListNode *next;

* };

*/

// 你需要完成以下的函数。

/**

求取两个单链表整数的和并且返回

@param l1 第一个单链表整数的个位数结构体地址

@param l2 第二个单链表整数的个位数结构体地址

@return 两个单链表整数的和的个位数结构体地址

*/

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {

   

}

这道题的网址为“https://leetcode.com/problems/add-two-numbers/#/description”。

---

作者: Miss_Allsunday    时间: 2017-6-14 11:17
以下是我的解答，这道题需要注意的是几个点，比如
(1 -> 2 -> 3) + (4 -> 2)
(1 -> 2 -> 9 -> 9) + (9 -> 7)
(3 -> 4 -> 8) + (5 -> 4 -> 2)
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode head = { -1, NULL };
    struct ListNode *current = &head;
    _Bool isOverflow = 0;
   
    while (l1 != NULL && l2 != NULL) {
        current->next = (struct ListNode *) malloc(sizeof(struct ListNode));
        current = current->next;
        
        current->val = l1->val + l2->val;
        
        if (isOverflow) {
            current->val += 1;
            isOverflow = 0;
        }
        
        if (current->val > 9) {
            isOverflow = 1;
            current->val %= 10;
        }
        
        l1 = l1->next;
        l2 = l2->next;
    }
   
    while (l1 != NULL) {
        current->next = (struct ListNode *) malloc(sizeof(struct ListNode));
        current = current->next;
        
        current->val = l1->val;
        l1 = l1->next;
        
        if (isOverflow) {
            current->val += 1;
            isOverflow = 0;
        }
        
        if (current->val > 9) {
            isOverflow = 1;
            current->val %= 10;
        }
    }
   
    while (l2 != NULL) {
        current->next = (struct ListNode *) malloc(sizeof(struct ListNode));
        current = current->next;
        
        current->val = l2->val;
        l2 = l2->next;
        
        if (isOverflow) {
            current->val += 1;
            isOverflow = 0;
        }
        
        if (current->val > 9) {
            isOverflow = 1;
            current->val %= 10;
        }
    }
   
    if (isOverflow) {
        current->next = (struct ListNode *) malloc(sizeof(struct ListNode));
        current->val = 1;
        isOverflow = 0;
    }
   
    return head.next;
}

---

作者: 呉HENG    时间: 2017-6-14 18:05
谢谢大神分享

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2