两数相加

题目

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。你可以假设除了数字 0 之外，这两个数字都不会以零开头。
例如：

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

分析

由于非负整数各位数在链表中是逆序存放的，假设存放非负整数a的链表是LA，存放非负整数b的链表是LB，存放a，b和的链表是LC；对LA，LB链表中相同序号的节点值相加，将结果存放在LC中相同序号的节点上，如果相加时产生了进位，则将进位加到LC的下一节点上

过程如下

• 将数a=76854309存放在LA中 数a.png
• 将数a=57941存放在LB中 数b.png

• 将LA，LB相同序号位相加，结果存放在LC中，如果相加是产生进位，则进位加到LC的下一节点上

  
  c.png

算法实现

//
//  main.m
//  add
//
//  Created by mye on 2018/5/12.
//  Copyright © 2018 mye. All rights reserved.
//

#import <Foundation/Foundation.h>

/**
 Definition for singly-linked list
 */
struct ListNode {
    int value;
    struct ListNode *next;
};

/**
 将链表l1和l2中存放的非负整数值的和存放在链表L中

 @param l1 存放的非负整数的链表
 @param l2 存放的非负整数的链表
 @return 返回链表L，L中存放链表l1和l2中的非负整数值的和
 */
struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2) {
    
    struct ListNode *headerA = l1->next;
    struct ListNode *headerB = l2->next;
    
    struct ListNode *L = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode *headerC = L;
    headerC->next = NULL;
    
    // 遍历链表
    while (headerA != NULL || headerB != NULL) {
        int sum = 0;
        if (headerC->next != NULL) {
            // 前一次求和计算有进位
            sum = headerC->next->value;
        }
        if (headerA != NULL) {
            // 加上l1节点的值
            sum += headerA->value;
            headerA = headerA->next;
        }
        if (headerB != NULL) {
            // 加上l1节点的值
            sum += headerB->value;
            headerB = headerB->next;
        }
        
        if (headerC->next != NULL) {
            // 前一次求和计算有进位
            int quotients = sum / 10;
            if (quotients) {
                // 本次求和计算有进位
                // 和值只保留余数
                sum = sum % 10;
                // 将进位值保持在新节点中
                struct ListNode *nextNode = (struct ListNode *)malloc(sizeof(struct ListNode));
                nextNode->value = quotients;
                nextNode->next = NULL;
                // 将新节点添加到L中
                headerC->next->next = nextNode;
            }
            // 将本次求和计算的值保持在当前节点中
            headerC->next->value = sum;
            headerC = headerC->next;
        } else {
            // 前一次求和计算无进位
            struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
            int quotients = sum / 10;
            if (quotients) {
                // 进位
                sum = sum % 10;
                // 将进位值保持在新节点中
                struct ListNode *nextNode = (struct ListNode *)malloc(sizeof(struct ListNode));
                nextNode->value = quotients;
                nextNode->next = NULL;
                // 将新节点添加到L中
                node->next = nextNode;
            } else {
                // 无进位
                node->next = NULL;
            }
            // 将本次求和计算的值保持在当前节点中
            node->value = sum;
            headerC->next = node;
            headerC = node;
        }
    }
    return L;
}

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // 数a
        long a = 99765437898;
        // 数b
        long b = 5741561071264;
        
        // 将数a存放在l1中
        struct ListNode *L1 = (struct ListNode *)malloc(sizeof(struct ListNode));
        struct ListNode *La = L1;
        La->next = NULL;
        while (a != 0) {
            int value = a % 10;
            struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
            node->value = value;
            node->next = NULL;
            La->next = node;
            La = node;
            a = a / 10;
        }
        
        // 将数b存放在l2中
        struct ListNode *L2 = (struct ListNode *)malloc(sizeof(struct ListNode));
        struct ListNode *Lb = L2;
        Lb->next = NULL;
        while (b != 0) {
            int value = b % 10;
            struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
            node->value = value;
            node->next = NULL;
            Lb->next = node;
            Lb = node;
            b = b / 10;
        }
        
        struct ListNode *L3 = addTwoNumbers(L1, L2);
        struct ListNode *header = L3->next;
        while (header != NULL) {
            printf("%d\n", header->value);
            header = header->next;
        }
        
        free(L1);
        free(L2);
        free(L3);
    }
    return 0;
}