两个整数求和链表返回链表

题目描述

给定两个表示两个非负整数的链表。数字是按照相反的顺序存储的，并且它们的每个节点包含单个数字。添加这两个数字并将其作为链表返回。

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

解法

这道题目的思路还是比较简单的，就是用两个指针分别遍历两个链表，每次将对应位置的数的和加上进位，最后将结果存在新的链表中。需要注意的是，如果最后还有进位，需要将进位加上去。

Python 代码

相关问题

用链表实现两个超大整数相加

假设我们有两个超大整数num1和num2，我们可以使用链表来存储它们，每个节点存储一个数字。为了方便计算，我们可以将链表尾部对齐，不足的地方用0填充。

首先，我们从链表头开始遍历两个链表，同时将每个节点的数字相加，并记录进位。如果某一链表先到达尾部，那么我们可以将其余部分视为0继续相加。最终，我们可以得到一个新的链表，它存储了相加后的结果。

需要注意的是，如果最高位有进位，我们需要在结果链表的头部添加一个节点，表示进位。

下面是代码实现：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def addTwoNumbers(self, num1: ListNode, num2: ListNode) -> ListNode:
        # 将链表对齐
        len1 = self.getLength(num1)
        len2 = self.getLength(num2)
        if len1 > len2:
            num2 = self.padList(num2, len1-len2)
        else:
            num1 = self.padList(num1, len2-len1)
        # 相加
        carry = 0
        dummy = ListNode()
        curr = dummy
        while num1:
            total = num1.val + num2.val + carry
            carry = total // 10
            curr.next = ListNode(total % 10)
            curr = curr.next
            num1 = num1.next
            num2 = num2.next
        # 处理最高位的进位
        if carry:
            curr.next = ListNode(carry)
        return dummy.next
        
    def getLength(self, head: ListNode) -> int:
        n = 0
        while head:
            n += 1
            head = head.next
        return n
    
    def padList(self, head: ListNode, n: int) -> ListNode:
        for i in range(n):
            head = ListNode(0, head)
        return head

时间复杂度为O(max(m,n))，其中m和n分别为两个链表的长度。空间复杂度为O(max(m,n))，因为我们需要创建一个新的链表来存储结果。

C语言合并两个有序链表 返回其中一个链表

好的，我理解了你的问题。

以下是C语言代码，它可以将两个有序链表合并成一个，并返回其中一个链表（假设第一个链表为返回链表）：

#include <stdio.h>
#include <stdlib.h>

// 定义链表结构体
typedef struct Node {
    int val;
    struct Node* next;
} Node;

// 合并两个有序链表
Node* merge(Node* l1, Node* l2) {
    // 定义返回链表和当前节点指针
    Node* ret = l1;
    Node* cur = l1;

    // 判断链表是否为空
    if (l1 == NULL) {
        return l2;
    }
    if (l2 == NULL) {
        return l1;
    }

    // 按照从小到大的顺序合并链表
    if (l1->val < l2->val) {
        cur = l1->next;
    } else {
        ret = l2;
        cur = l2->next;
        l2 = l1;
        l1 = ret;
    }

    Node* prev = ret;
    while (cur != NULL && l2 != NULL) {
        if (l2->val < cur->val) {
            prev->next = l2;
            l2 = l2->next;
            prev = prev->next;
            prev->next = cur;
        } else {
            prev = cur;
            cur = cur->next;
        }
    }

    // 将剩余的节点添加到链表中
    if (l2 != NULL) {
        prev->next = l2;
    }

    // 返回链表
    return ret;
}

// 创建新节点
Node* createNode(int val) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->val = val;
    newNode->next = NULL;
    return newNode;
}

// 输出链表
void printList(Node* head) {
    Node* cur = head;
    while (cur != NULL) {
        printf("%d ", cur->val);
        cur = cur->next;
    }
    printf("\n");
}

int main() {
    // 创建两个有序链表
    Node* l1 = createNode(1);
    l1->next = createNode(3);
    l1->next->next = createNode(5);

    Node* l2 = createNode(2);
    l2->next = createNode(4);
    l2->next->next = createNode(6);

    // 输出两个链表
    printf("l1: ");
    printList(l1);

    printf("l2: ");
    printList(l2);

    // 合并链表并输出
    Node* ret = merge(l1, l2);
    printf("merged: ");
    printList(ret);

    return 0;
}

这段代码中，我们首先定义了一个链表的结构体 `Node`，然后定义了合并两个有序链表的函数 `merge`。在函数中，我们先判断了链表是否为空，并根据两个链表的节点值的大小比较，确定了返回链表和当前节点指针的初始值。接着，我们使用 `while` 循环来合并两个链表，直到其中一个链表为空。对于每一个节点值较小的链表节点，我们都将它插入到返回链表中，直到两个链表中有一个为空。最后，我们将剩余的节点加入到链表中，并返回返回链表的头指针。

在 `main` 函数中，我们创建了两个有序链表 `l1` 和 `l2`，并输出它们的值。然后，我们调用 `merge` 函数将两个链表合并，并输出合并后的链表。