leetcode2两数相加题目

两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

eg：单向链表的建立
#include <stdio.h>
#include <stdlib.h>

struct link *AppendNode (struct link *head);
void DisplyNode (struct link *head);
void DeletMemory (struct link *head);

struct link
{
    int data;
    struct link *next;
};

int main(void)
{
    int i = 0;
    char c;
    struct link *head = NULL;    //链表头指针
    printf("Do you want to append a new node(Y/N)?");
    scanf_s(" %c", &c);
    while (c == 'Y' || c == 'y')
    {
        head = AppendNode(head);//向head为头指针的链表末尾添加节点
        DisplyNode(head);        //显示当前链表中的各节点的信息
        printf("Do your want to append a new node(Y/N)");
        scanf_s(" %c", &c);
        i++;
    }
    printf("%d new nodes have been apended", i);
    DeletMemory(head);    //释放所有动态分配的内存

    return 0;
}
/* 函数功能：新建一个节点并添加到链表末尾，返回添加节点后的链表的头指针 */
struct link *AppendNode(struct link *head)
{
    struct link *p = NULL, *pr = head;
    int data;
    p = (struct link *)malloc(sizeof(struct link));//让p指向新建的节点
    if (p == NULL)        //若新建节点申请内存失败，则退出程序
    {
        printf("No enough memory to allocate\n");
        exit(0);
    }
    if (head == NULL)    //若原链表为空表
    {
        head = p;        //将新建节点置为头节点
    }
    else                //若原链表为非空，则将新建节点添加到表尾
    {
        while (pr->next != NULL)//若未到表尾，则移动pr直到pr指向表尾
        {
            pr = pr->next;        //让pr指向下一个节点
        }
        pr->next = p;            //让末节点的指针指向新建的节点
    }
    printf("Input node data\n");
    scanf_s("%d", &data); //输入节点数据
    p->data = data;        //将新建节点的数据域赋值为输入的节点数据值
    p->next = NULL;        //将新建的节点置为表尾
    return head;        //返回添加节点后的链表的头指针
}
/* 函数的功能：显示链表中所有节点的节点号和该节点中的数据项的内容*/
void DisplyNode (struct link *head)
{
    struct link *p = head;
    int j = 1;
    while (p != NULL)  //若不是表尾，则循环打印节点的数值
    {
        printf("%5d%10d\n", j, p->data);//打印第j个节点数据
        p = p->next;  //让p指向下一个节点
        j++;
    }
}
//函数的功能：释放head所指向的链表中所有节点占用的内存
void DeletMemory(struct link *head)
{
    struct link *p = head, *pr = NULL;
    while (p != NULL)  //若不是表尾，则释放节点占用的内存
    {
        pr = p;        //在pr中保存当前节点的指针
        p = p->next;//让p指向下一个节点
        free(pr);    //释放pr指向的当前节点占用的内存
    }
}
上面的代码使用了三个函数AppendNode、DisplyNode、DeletMemory

struct link *AppendNode (struct link *head);（函数作用：新建一个节点并添加到链表末尾，返回添加节点后的链表的头指针）

void DisplyNode (struct link *head);（函数功能：显示链表中所有节点的节点号和该节点中的数据项的内容）

void DeletMemory (struct link *head);（函数功能：释放head所指向的链表中所有节点占用的内存）

---

C++

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    int flag = 0, nodeSum = 0, freeflag = 0;
    struct ListNode *ret,*now,*high,*freeBegin,*freeEnd;
    for(ret = l1, now = l1, high = l2, freeBegin = l2;l1  || l2  || flag ;) {  
        if (l1 == NULL && l2 == NULL) {
              now->next = high;
              now = now->next;
              freeBegin = now->next;
        }
        nodeSum = ( l1  ? l1->val : 0 ) + (l2 ? l2->val : 0) + flag;  
        now->val = nodeSum % 10;    
        flag =  nodeSum / 10; 
        l1 ? l1 = (l1->next ? l1->next : NULL) : NULL;
        if(l1 == NULL && 0 == freeflag && l2) {
            freeEnd = l2;
            freeflag = 1;
        }
        l2 ? l2 = (l2->next ? l2->next : NULL) : NULL;
        now->next = ( l1 ? l1 : (l2 ?  l2 : NULL) );
        now->next ? now = now->next : NULL;
    }
    l2 = freeBegin;
    freeEnd->next = NULL;
    return ret;
}

---

python

---

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        root = ListNode(0) # 初始化头节点
        node = root 
        num = 0 # 每次相加的进位

        # 循环走l1、l2，每次各一个节点
        while l1 is not None and l2 is not None:
            s = l1.val + l2.val + num # 两数相加并加上进位
            node.next = ListNode(s % 10) # 添加新节点
            num = s // 10 # 新的进位
            l1 = l1.next
            l2 = l2.next
            node = node.next
        
        # l2已经走完，l1还有节点，示例：(2 -> 4 -> 3) + (5 -> 6)
        if l1 is not None:
            while l1 is not None:
                s = l1.val + num
                node.next = ListNode(s % 10)
                num = s // 10
                node = node.next
                l1 = l1.next

        # l1已经走完，l2还有节点，示例：(2 -> 4) + (5 -> 6 -> 7)
        if l2 is not None:
            while l2 is not None:
                s = l2.val + num
                node.next = ListNode(s % 10)
                num = s // 10
                node = node.next
                l2 = l2.next

        # 最后进位为1时，还要添加一个节点，示例：(2 -> 5) + (3 -> 6)
        if num == 1:
            node.next = ListNode(1)
        
        return root.next

---