当前位置：极客教程 > C++语言 > C++ 示例 > C++程序 链表表示的两个数字相加-第1部分

C++程序 链表表示的两个数字相加-第1部分

C++程序 链表表示的两个数字相加-第1部分

给定两个由链表表示的数字，编写一个函数返回它们的和的链表。和列表是两个输入数字的加法列表表示形式。

例子 :

输入：
List1: 5->6->3 //表示数字：563
List2: 8->4->2 //表示数字：842
输出：
结果列表：1->4->0->5 // 表示数字：1405
解释： 563 + 842 = 1405

输入：
List1: 7->5->9->4->6 //表示数字：75946
List2: 8->4 //表示数字：84
输出：
结果列表：7->6->0->3->0 //表示数字：76030
解释： 75946+84=76030

方法1：

方法 : 遍历两个列表，逐个选择两个列表的节点并添加其值。如果和大于10，则将进位设置为1并减少总和。如果一个列表的元素比另一个列表的元素多，则将该列表的剩余值视为0。具体步骤如下：

  1. 从开始到结束遍历两个链接列表。
  2. 分别从相关链表中添加两个数字。
  3. 如果其中一个列表已经到达末尾，则将其数字取为0。
  4. 一直执行到两个列表的末尾。
  5. 如果两个数字之和大于9，则将进位设置为1，并将当前数字设置为 sum % 10

以下是此方法的实现。

// C++程序：实现用链表表示的两数相加
#include
using namespace std;
 
// 链表节点
class Node
{
    public:
    int data;
    Node* next;
};
 
/* 创建一个带有给定数据的新节点的函数 */
Node* newNode(int data)
{
    Node* new_node = new Node();
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}
 
/* 插入一个节点到单链表的开始 */
void push(Node** head_ref, int new_data)
{
    // 分配节点
    Node* new_node = newNode(new_data);
 
    // 将新节点连接到旧列表中
    new_node->next = (*head_ref);
 
    // 把头指针移动到新节点
    (*head_ref) = new_node;
}
 
/* 对两个链表的内容相加，并返回结果链表的头节点指针 */
Node* addTwoLists(Node* first,Node* second)
{
    // res是结果链表的头节点指针
    Node* res = NULL;
    Node *temp, *prev = NULL;
    int carry = 0, sum;
 
    // 只要两个链表存在，就循环执行
    while (first != NULL || second != NULL)
    {
        // 计算结果链表的下一位数字的值。下一位数字的值是以下内容的总和
        // (i) 进位的值
        // (ii) 第一个链表的下一位数字（如果有的话）
        // (ii) 第二个链表的下一位数字（如果有的话）
        sum = carry + (first ? first->data : 0) + (second ? second->data : 0);
 
        // 更新进位的值，用于下次计算
        carry = (sum >= 10) ? 1 : 0;
 
        // 如果总和大于等于10，更新总和
        sum = sum % 10;
 
        // 创建带有总和为数值的新节点
        temp = newNode(sum);
 
        // 如果这是第一个节点，设置它为结果链表的头节点
        if (res == NULL)
            res = temp;
 
        // 如果这不是第一个节点，则把新节点链接到剩下的节点
        else
            prev->next = temp;
 
        // 设置下一次插入的prev值
        prev = temp;
 
        // 将第一个和第二个指针指向下一个节点
        if (first)
            first = first->next;
        if (second)
            second = second->next;
    }
 
    if (carry > 0)
        temp->next = newNode(carry);
 
    // 返回结果链表的头节点指针
    return res;
}
 
// 打印单向链表的实用程序函数
void printList(Node* node)
{
    while (node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}
 
// 主函数
int main(void)
{
    Node* res = NULL;
    Node* first = NULL;
    Node* second = NULL;
 
    // 创建第一个链表 7->5->9->4->6
    push(&first;, 6);
    push(&first;, 4);
    push(&first;, 9);
    push(&first;, 5);
    push(&first;, 7);
    printf("First List is ");
    printList(first);
 
    // 创建第二个链表 8->4
    push(&second;, 4);
    push(&second;, 8);
    cout << "Second List is ";
    printList(second);
 
    // 把两个链表相加并查看结果
    res = addTwoLists(first, second);
    cout << "Resultant list is ";
    printList(res);
    return0;
}

输出：

第一个列表是 7 5 9 4 6
第二个列表是 8 4
结果列表是 5 0 0 5 6

复杂度分析：

  • 时间复杂度: O(m + n)，其中m和n分别为第一个和第二个列表中的节点数。 列表只需要遍历一次。
  • 空间复杂度: O(m + n)。 需要一个临时链表来存储输出数字

方法2(使用STL): 使用堆栈数据结构

方法:

  1. 创建3个堆栈，分别为s1，s2，s3。
  2. 使用list1中的节点填充s1，并使用list2中的节点填充s2。
  3. 使用新节点填充s3，并将新节点的数据设置为s1.top()，s2.top()和进位的和，直到list1和list2为空为止。
  4. 如果和大于9，则设置进位为1。
  5. 否则设置进位为0。
  6. 创建一个包含总和列表头的节点(称为prev)。
  7. 将s3中的所有元素从顶部到底部链接。
  8. 返回prev。
// C++程序，通过使用堆栈将由链表表示的两个数字相加
#include <bits/stdc++.h>
using namespace std;
class Node
{
    public:
    int data;
    Node* next;
};
Node* newnode(int data)
{
    Node* x = new Node();
    x->data = data;
    return x;
}
// 函数返回由链表表示的两个数字的和
Node* addTwoNumbers(Node* l1, Node* l2)
{
    Node* prev = NULL;

    // 创建三个堆栈
    stack<Node*> s1, s2, s3;

    // 填充第一个堆栈与第一个列表元素
    while (l1 != NULL)
    {
        s1.push(l1);
        l1 = l1->next;
    }

    // 填充第二个堆栈与第二个列表元素
    while (l2 != NULL)
    {
        s2.push(l2);
        l2 = l2->next;
    }
    int carry = 0;
    // 填充第三个堆栈与前两个堆栈的和
    while (!s1.empty() && !s2.empty())
    {
        int sum = (s1.top()->data +
                   s2.top()->data + carry);
        Node* temp = newnode(sum % 10);
        s3.push(temp);
        if (sum > 9)
        {
            carry = 1;
        }
        else
        {
            carry = 0;
        }
        s1.pop();
        s2.pop();
    }
    while (!s1.empty())
   {
        int sum = carry + s1.top()->data;
        Node* temp = newnode(sum % 10);
        s3.push(temp);
        if (sum > 9)
        {
            carry = 1;
        }
        else
        {
            carry = 0;
        }
        s1.pop();
    }
    while (!s2.empty())
    {
        int sum = carry + s2.top()->data;
        Node* temp = newnode(sum % 10);
        s3.push(temp);
        if (sum > 9)
        {
            carry = 1;
        }
        else
        {
            carry = 0;
        }
        s2.pop();
    }
    // 如果进位仍然存在，则创建一个新的值为1的节点并将其推到第三个堆栈
    if (carry == 1)
    {
        Node* temp = newnode(1);
        s3.push(temp);
    }

    // 将第三个堆栈中的所有元素链接在一起
    if (!s3.empty())
        prev = s3.top();
    while (!s3.empty())
    {
        Node* temp = s3.top();
        s3.pop();
        if (s3.size() == 0)
        {
            temp->next = NULL;
        }
        else
        {
            temp->next = s3.top();
        }
    }
    return prev;
}

// 实用程序函数
// 显示链表的函数
void Display(Node* head)
{
    if (head == NULL)
    {
        return;
    }
    while (head->next != NULL)
    {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << head->data << endl;
}

// 在链表末尾添加元素的函数
void push(Node** head_ref, int d)
{
    Node* new_node = newnode(d);
    new_node->next = NULL;
    if (*head_ref == NULL)
    {
        new_node->next = *head_ref;
        *head_ref = new_node;
        return;
    }
    Node* last = *head_ref;
    while (last->next != NULL &&
           last != NULL)
    {
        last = last->next;
    }
    last->next = new_node;
    return;
}

// driver函数
int main()
{
    // 创建两个列表，第一个列表为9->5->0，第二个列表为6->7
    Node* first = NULL;
    Node* second = NULL;
    Node* sum = NULL;
    push(&first, 9);
    push(&first, 5);
    push(&first, 0);
    push(&second, 6);
    push(&second, 7);
    cout << "First List : ";
    Display(first);
    cout << "Second List : ";
    Display(second);
    sum = addTwoNumbers(first, second);
    cout << "Sum List : ";
    Display(sum);
    return 0;
}

输出:

First List : 9 -> 5 -> 0
Second List : 6 -> 7
Sum List : 1 -> 0 -> 1 -> 7

时间复杂度： O(n)，其中n是两个链表中较长者的长度。

空间复杂度： O(n)，其中n是两个链表中较长者的长度。我们使用两个堆栈来存储两个链表的节点，总共占用O(n)的空间。

另一种时间复杂度为O(N)的方法：

给定方法的步骤如下：

  1. 首先，我们分别计算两个链表的大小，size1和size2。
  2. 然后，我们遍历较长的链表（如果有的话），并将其递减直到两个链表的大小相同。
  3. 现在我们遍历两个链表直到结束。
  4. 现在在执行加法时回溯。
  5. 最后，返回包含答案的链表的头节点。
// C++ program to add two numbers
// represented by linked list
#include <bits/stdc++.h>
using namespace std;

// Linked list node
class Node
{
    public:
    int data;
    Node* next;
};

/* Function to create a
new node with given data */
Node* newNode(int data)
{
    Node* new_node = new Node();
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

/* Function to insert a node at the
beginning of the Singly Linked List */
void push(Node** head_ref, int new_data)
{
    // Allocate node
    Node* new_node = newNode(new_data);

    // link the old list of the
    // new node
    new_node->next = (*head_ref);

    // Move the head to point to the
    // new node
    (*head_ref) = new_node;
}

/* Adds contents of two linked lists and
return the head node of resultant list */
Node* addTwoLists(Node* first,
                Node* second)
{
    // res is head node of the resultant
    // list
    Node* res = NULL;
    Node *temp, *prev = NULL;
    int carry = 0, sum;

    // while both lists exist
    while (first != NULL ||
        second != NULL)
    {
        // Calculate value of next digit in
        // resultant list. The next digit is
        // sum of following things
        // (i) Carry
        // (ii) Next digit of first
        // list (if there is a next digit)
        // (ii) Next digit of second
        // list (if there is a next digit)
        sum = carry + (first ? first->data : 0) +
            (second ? second->data : 0);

        // Update carry for next calculation
        carry = (sum >= 10) ? 1 : 0;

        // Update sum if it is greater than 10
        sum = sum % 10;

        // Create a new node with sum as data
        temp = newNode(sum);

        // If this is the first node then
        // set it as head of the resultant list
        if (res == NULL)
            res = temp;

        // If this is not the first
        // node then connect it to the rest.
        else
            prev->next = temp;

        // Set prev for next insertion
        prev = temp;

        // Move first and second
        // pointers to next nodes
        if (first)
            first = first->next;
        if (second)
            second = second->next;
    }

    if (carry > 0)
        temp->next = newNode(carry);

    // return head of the resultant
    // list
    return res;
}

// A utility function to print a
// linked list
void printList(Node* node)
{
    while (node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}

// Driver code
int main(void)
{
    Node* res = NULL;
    Node* first = NULL;
    Node* second = NULL;

    // Create first list
    // 7->5->9->4->6
    push(&first, 6);
    push(&first, 4);
    push(&first, 9);
    push(&first, 5);
    push(&first, 7);
    printf("First List is ");
    printList(first);

    // Create second list 8->4
    push(&second, 4);
    push(&second, 8);
    cout << "Second List is ";
    printList(second);

    // Add the two lists and see
    // result
    res = addTwoLists(first,
                    second);
    cout << "Resultant list is ";
    printList(res);
    return 0;
}

输出:

第一个链表：5 -> 6 -> 3
第二个链表：8 -> 4 -> 2
求和链表：1 -> 4 -> 0 -> 5

时间复杂度： O(n)，因为我们遍历两个链表并添加数字，直到我们到达较长链表的末尾。

空间复杂度： : O(1)，因为我们只使用单个节点来存储当前节点中两个数字的总和。

Python教程

Python 教程

Python 教程
Tkinter 教程

Tkinter 教程
Pandas 教程

Pandas 教程
NumPy 教程

NumPy 教程
Flask 教程

Flask 教程
Django 教程

Django 教程
PySpark 教程

PySpark 教程
wxPython 教程

wxPython 教程
SymPy 教程

SymPy 教程
Seaborn 教程

Seaborn 教程
SciPy 教程

SciPy 教程
RxPY 教程

RxPY 教程
Pycharm 教程

Pycharm 教程
Pygame 教程

Pygame 教程
PyGTK 教程

PyGTK 教程
PyQt 教程

PyQt 教程
PyQt5 教程

PyQt5 教程
PyTorch 教程

PyTorch 教程
Matplotlib 教程

Matplotlib 教程
Web2py 教程

Web2py 教程
BeautifulSoup 教程

BeautifulSoup 教程

Java教程

Java 教程

Java 教程

Web教程

HTML 教程

HTML 教程
CSS 教程

CSS 教程
CSS3 教程

CSS3 教程
jQuery 教程

jQuery 教程
Ajax 教程

Ajax 教程
AngularJS 教程

AngularJS 教程
TypeScript 教程

TypeScript 教程
WordPress 教程

WordPress 教程
Laravel 教程

Laravel 教程
Next.js 教程

Next.js 教程
PhantomJS 教程

PhantomJS 教程
Three.js 教程

Three.js 教程
Underscore.JS 教程

Underscore.JS 教程
WebGL 教程

WebGL 教程
WebRTC 教程

WebRTC 教程
VueJS 教程

VueJS 教程

数据库教程

SQL 教程

SQL 教程
MySQL 教程

MySQL 教程
MongoDB 教程

MongoDB 教程
PostgreSQL 教程

PostgreSQL 教程
SQLite 教程

SQLite 教程
Redis 教程

Redis 教程
MariaDB 教程

MariaDB 教程

图形图像教程

Vulkan 教程

Vulkan 教程
OpenCV 教程

OpenCV 教程

大数据教程

R语言 教程

R语言 教程

开发工具教程

Git 教程

Git 教程
VSCode 教程

VSCode 教程
Docker 教程

Docker 教程
Gerrit 教程

Gerrit 教程
Excel 教程

Excel 教程

计算机教程

Go语言 教程

Go语言 教程
C++ 教程

C++ 教程

C++ 示例