首页 > itarticle > 数据结构单链表之将链表表示的两个数字相加第十四套

数据结构单链表之将链表表示的两个数字相加第十四套

admin 12月 22, 2021 0

小知识，大挑战！本文正在参与“程序员必备小知识”创作活动。

给定由两个列表表示的两个数字，编写一个返回总和列表的函数。总和列表是两个输入数字相加的列表表示。

示例：

输入： 
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

方法：从末尾遍历两个列表，并一一选择两个列表的节点并添加值。如果总和大于 10，则进位为 1 并减少总和。如果一个列表的元素多于另一个，则将此列表的剩余值视为 0。反转最终列表以获得总和。

步骤是： 

  1. 从头到尾遍历两个链表。
  2. 分别从各自的链表中添加两位数字。
  3. 如果其中一个列表已到达末尾，则取 0 作为其数字。
  4. 继续它直到列表的末尾。
  5. 如果两位数之和大于 9，则将进位设置为 1，将当前位数设置为和 % 10反转结果列表以获得实际和。

下面是这个方法的实现。

#include <bits/stdc++.h>
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)
{
	Node* res = NULL;
	Node *temp, *prev = NULL;
	int carry = 0, sum;

	while (first != NULL
		|| second != NULL) {
		
		sum = carry + (first ? first->data : 0)
			+ (second ? second->data : 0);

		carry = (sum >= 10) ? 1 : 0;

		sum = sum % 10;

		temp = newNode(sum);

		if (res == NULL)
			res = temp;

		else
			prev->next = temp;

		prev = temp;

		if (first)
			first = first->next;
		if (second)
			second = second->next;
	}

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

	return res;
}

Node* reverse(Node* head)
{
	if (head == NULL || head->next == NULL)
		return head;

	Node* rest = reverse(head->next);
	head->next->next = head;

	head->next = NULL;

	return rest;
}

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;

	push(&first, 6);
	push(&first, 4);
	push(&first, 9);
	push(&first, 5);
	push(&first, 7);
	printf("First List is ");
	printList(first);

	push(&second, 4);
	push(&second, 8);
	cout << "Second List is ";
	printList(second);

	first = reverse(first);
	second = reverse(second);

	res = addTwoLists(first, second);

	res = reverse(res);
	cout << "Resultant list is ";
	printList(res);

	return 0;
}
复制代码

输出

First List is 7 5 9 4 6 
Second List is 8 4 
Resultant list is 5 0 0 5 6 
复制代码

复杂度分析： 

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

方法二（Using STL）： 使用栈数据结构

方法 ：

  • 创建 3 个堆栈，即 s1、s2、s3。

  • 用 list1 的节点填充 s1，用 list2 的节点填充 s2。

  • 通过创建新节点并将新节点的数据设置为 s1.top()、s2.top() 的总和来填充 s3，并进位直到 list1 和 list2 为空。

  • 如果总和 >9

    • 设置进位 1

  • 别的

    • 设置进位 0

  • 创建一个包含总和列表头部的节点（比如上一个）。

  • 从上到下链接s3的所有元素

  • 返回上一页

代码：

#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();
	}
	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;
}
int main()
{
	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) 的方法：

 
 给定的方法按以下步骤工作：

  1. 首先，我们分别计算链表 size1 和 size2 的大小。
  2. 然后我们遍历更大的链表，如果有的话，递减直到两者的大小相同。
  3. 现在我们遍历两个链表直到结束。
  4. 现在在执行加法时发生回溯。
  5. 最后，返回包含答案的链表的头节点。
#include <iostream>
using namespace std;

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

Node* addition(Node* temp1, Node* temp2, int size1,
			int size2)
{
	Node* newNode
		= (struct Node*)malloc(sizeof(struct Node));

	if (temp1->next == NULL && temp2->next == NULL) {

		newNode->data = (temp1->data + temp2->data);
		newNode->next = NULL;
		return newNode;
	}

	Node* returnedNode
		= (struct Node*)malloc(sizeof(struct Node));

	if (size2 == size1) {
		returnedNode = addition(temp1->next, temp2->next,
								size1 - 1, size2 - 1);

		newNode->data = (temp1->data + temp2->data)
						+ ((returnedNode->data) / 10);
	}
	else {
		returnedNode = addition(temp1, temp2->next, size1,
								size2 - 1);
		newNode->data
			= (temp2->data) + ((returnedNode->data) / 10);
	}
	returnedNode->data = (returnedNode->data) % 10;

	newNode->next = returnedNode;
	return newNode;
}
struct Node* addTwoLists(struct Node* head1,
						struct Node* head2)
{
	struct Node *temp1, *temp2, *ans = NULL;

	temp1 = head1;
	temp2 = head2;

	int size1 = 0, size2 = 0;
	while (temp1 != NULL) {
		temp1 = temp1->next;
		size1++;
	}
	while (temp2 != NULL) {
		temp2 = temp2->next;
		size2++;
	}

	Node* returnedNode
		= (struct Node*)malloc(sizeof(struct Node));
	if (size2 > size1) {
		returnedNode = addition(head1, head2, size1, size2);
	}
	else {
		returnedNode = addition(head2, head1, size2, size1);
	}
	if (returnedNode->data >= 10) {
		ans = (struct Node*)malloc(sizeof(struct Node));
		ans->data = (returnedNode->data) / 10;
		returnedNode->data = returnedNode->data % 10;
		ans->next = returnedNode;
	}
	else
		ans = returnedNode;

	return ans;
}

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
		= (struct Node*)malloc(sizeof(struct Node));
	new_node->data = 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;
}
int main()
{
	// Creating two lists
	Node* first = NULL;
	Node* second = NULL;
	Node* sum = NULL;
	push(&first, 5);
	push(&first, 6);
	push(&first, 3);
	push(&second, 8);
	push(&second, 4);
	push(&second, 2);
	cout << "First List : ";
	Display(first);
	cout << "Second List : ";
	Display(second);
	sum = addTwoLists(first, second);
	cout << "Sum List : ";
	Display(sum);
	return 0;
}
复制代码

输出

First List : 5 -> 6 -> 3
Second List : 8 -> 4 -> 2
Sum List : 1 -> 4 -> 0 -> 5
复制代码

🥇 往期优质文章

数据结构单链表之链表介绍 | 第一套
数据结构单链表之链表与数组 | 第二套
数据结构单链表之链表插入 | 第三套
数据结构单链表之删除节点 | 第四套
数据结构单链表之删除给定位置的链表节点 | 第五套
数据结构单链表之查看数组与链表的方法 | 第六套-1
数据结构单链表之查看数组与链表的方法 | 第六套-2
数据结构单链表之查找链表的长度（迭代和递归） | 第七套
数据结构单链表之交换链表中的节点而不交换数据 | 第八套
数据结构单链表之反转链表 | 第九套
数据结构单链表之合并两个已排序的链表 | 第十套
数据结构单链表之链表的归并排序 | 第十一套
数据结构单链表之以给定大小的组反转链表 | 第十二套
数据结构单链表之检测和删除链表中的循环 | 第十三套

📣尾注：
想要获取更多数据结构相关的知识，你可以关注我：海拥，我希望你觉得这篇文章有帮助。

如果你看到这里，感谢你的阅读 🙂

💌 欢迎大家在评论区提出意见和建议！💌

如果你真的从这篇文章中学到了一些新东西，喜欢它，收藏它并与你的小伙伴分享。🤗最后，不要忘了❤或📑支持一下哦。

微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能