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教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例