LeetCode第二题

题目描述：给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储 一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/add-two-numbers

思路

因为加数和被加数都是用链表表示的，且链表每个节点保存一位，按低位到高位组织。所以可以定义一个新链表Newlist，用来保存和。用两个指针分别指向两链表的首节点，同时往后遍历，取节点的值求和并保存在Newlist中。用carry暂存进位，采用尾插法建立Newlist。最后若最高位还有进位，则还需申请一个节点存一个值为1的最高位。

源码

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


struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    int carry = 0;          //暂存进位
    int sum = 0;
    struct ListNode* Newlist=malloc(sizeof(struct ListNode));
    struct ListNode* near = Newlist;
    near -> next = NULL;
    while(l1 && l2){
        sum = (l1 -> val) + (l2 -> val) + carry;
        struct ListNode* p=malloc(sizeof(struct ListNode));
        if(sum < 10){
            carry = 0;      //无进位
            p -> val = sum;
        }
        else{
            carry = 1;      //有进位
            p -> val = sum - 10;
        }
        p -> next = near -> next;
        near -> next = p;
        near = p;
        l1 = l1 -> next;
        l2 = l2 -> next;
    }
    while(l1){
        sum = (l1 -> val) + carry;
        struct ListNode* p=malloc(sizeof(struct ListNode));
        if(sum < 10){
            carry = 0;      //无进位
            p -> val = sum;
        }
        else{
            carry = 1;      //有进位
            p -> val = sum - 10;
        }
        p -> next = near -> next;
        near -> next = p;
        near = p;
        l1 = l1 -> next;
    }
    while(l2){
        sum = (l2 -> val) + carry;
        struct ListNode* p=malloc(sizeof(struct ListNode));
        if(sum < 10){
            carry = 0;      //无进位
            p -> val = sum;
        }
        else{
            carry = 1;      //有进位
            p -> val = sum - 10;
        }
        p -> next = near -> next;
        near -> next = p;
        near = p;
        l2 = l2 -> next;
    }
    if(carry == 1){         //最高位还有进位
        struct ListNode* p=malloc(sizeof(struct ListNode));
        p -> val = 1;
        p -> next = near -> next;
        near -> next = p;
    }
    return Newlist -> next;
}

复杂度分析

从前往后一次遍历完成，故时间复杂度为O（n）。
额外建立了链表，空间复杂度为O（n）。

处理进位的其他手法

可以不在每位求和的时候判断进位，而是直接将两数的和保存在Newlist节点。等Newlist链表创建完毕，再遍历一次Newlist，发现值大于等于10的节点，则其后节点的值加1且本节点减10。对于最后一个节点单独处理，若大于10，则在尾部添加一个值为1的节点。