首页 > 代码库 > LeetCode OJ 2. Add Two Numbers

LeetCode OJ 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

解答

寒假刷的第一题……

相当于是实现一个全加器阵列……大概是还没有走出数逻的阴影……

当然局部变量要记得初始化,将Carry变量赋值为0,这样链表头节点的相加就可以归入链表中一般节点的相加,将Ans赋值为NULL,为循环中链表的插入做准备,每一位都要加上前一位Carry的值并重新计算Carry,第一位的前一位Carry的值是0,最后一位相加也要重新计算Carry,并且如果两个链表长度不同,程序进行到后面只对一个链表进行计算时,每一位也要加上前一位Carry的值并重新计算Carry,因为可能存在9+999999的情况,其实这样的情况也就相当于是一个全加器单元的一个加数是0,并且最后一位相加结束后Carry不为0,则要再增加一位。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *Ans, *TempNode, *TailNode;
    int Carry;
    
    Carry = 0;
    Ans = TailNode = NULL;
    while(NULL != l1 && NULL != l2){
        TempNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        TempNode->val = (Carry + l1->val + l2->val) % 10;
        TempNode->next = NULL;
        Carry = (Carry + l1->val + l2->val) / 10;
        if(NULL == Ans){
            Ans = TempNode;
            TailNode = TempNode;
        }
        else{
            TailNode->next = TempNode;
            TailNode = TailNode->next;
        }
        l1 = l1->next;
        l2 = l2->next;
    }
    while(NULL != l1){
        TempNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        TempNode->val = (Carry + l1->val) % 10;
        TempNode->next = NULL;
        Carry = (Carry + l1->val) / 10;
        TailNode->next = TempNode;
        TailNode = TailNode->next;
        l1 = l1->next;
    }
    while(NULL != l2){
        TempNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        TempNode->val = (Carry + l2->val) % 10;
        TempNode->next = NULL;
        Carry = (Carry + l2->val) / 10;
        TailNode->next = TempNode;
        TailNode = TailNode->next;
        l2 = l2->next;
    }
    if(0 != Carry){
        TempNode = (struct ListNode*)malloc(sizeof(struct ListNode));
        TempNode->val = Carry;
        TempNode->next = NULL;
        TailNode->next = TempNode;
    }
    
    return Ans;
}

 

LeetCode OJ 2. Add Two Numbers