Singly linked list data structure will represent the list of the two Numbers together | 14 sets

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Given two numbers represented by two lists, write a function that returns a list of sums. A summation list is a tabulated representation of the addition of two input numbers.

Example:

Input: list1:5 ->6->3 // Number 563 List2:8 ->4->2 // Number 842 Output: List of results: 1->4->0->5 // Number 1405 Description: 563 + 842 = 1405

Input: List1: 7->5->9->4->6 // Number 75946 List2: 8->4 // Number 84 Output: List of results: 7->6->0->3-> 0// Number 76030 Description: 75946+84=76030

Method: Iterate through both lists from the end, selecting each node and adding values. If the sum is greater than 10, carry 1 and reduce the sum. If one list has more elements than the other, the rest of the list is treated as 0. Reverse the final list to get the sum.

Steps are:

1. Walk through two linked lists from beginning to end.
2. Add two digits from their respective lists.
3. If one of the lists has reached the end, take 0 as its number.
4. Continue it to the end of the list.
5. If the sum of the two digits is greater than 9, the carry is set to 1 and the current digit is set toAnd % 10Reverse the result list to get the actual sum.

The following is an implementation of this method.

#include <bits/stdc++.h>
using namespace std;

class Node {
public:
	int data;
	Node* next;
};

Node* newNode(int data)
{
	Node* new_node = new Node(a); 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;
}
Copy the code

The output

First List is 7 5 9 4 6 
Second List is 8 4 
Resultant list is 5 0 0 5 6 
Copy the code

Complexity analysis:

• Time complexity: O(m + n), where m and n are the number of nodes in the first and second lists, respectively. The list only needs to be traversed once.
• Space complexity: O(m + N). A temporary linked list is required to store the output numbers

Using STL: Use stack data structures

Methods:

• Create three stacks, s1, S2, s3.

• Fill S1 with the nodes of list1 and s2 with the nodes of list2.

• S3 is populated by creating a new node and setting its data to the sum of s1.top(), s2.top(), and carrying until list1 and list2 are empty.

• If the sum is greater than 9

  • Set carry 1

• other

  • Set carry 0

• Create a node that contains the head of the summation list (such as the previous one).

• Link all elements of S3 from top to bottom

• Return to previous page

Code:

#include <bits/stdc++.h>
using namespace std;
class Node {
public:
	int data;
	Node* next;
};
Node* newnode(int data)
{
	Node* x = new Node(a); 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(a); s2.pop(a); }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(a); }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(a); }if (carry == 1) {
		Node* temp = newnode(1);
		s3.push(temp);
	}
	if(! s3.empty())
		prev = s3.top(a);while(! s3.empty()) {
		Node* temp = s3.top(a); s3.pop(a);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(a)
{
	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;
}
Copy the code

The output

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

Another time complexity O(N) method:

The given method works as follows:

1. First, we calculate the sizes of linked lists size1 and size2, respectively.
2. We then iterate over larger lists, decreasing if any, until both are the same size.
3. Now let’s go through both lists until we finish.
4. Backtracking now occurs during addition.
5. Finally, the head node of the list containing the answer is returned.

#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(a)
{
	// 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;
}
Copy the code

The output

First List : 5 -> 6 -> 3
Second List : 8 -> 4 -> 2
Sum List : 1 -> 4 -> 0 -> 5
Copy the code

🥇 past quality articles

Singly linked list data structure of the chain table from the introduction of | first set of singly linked list data structure linked list and array | second singly linked list data structure of chain table insert | | delete nodes of the third set of singly linked list data structure of the fourth set of singly linked list data structure to delete a given location linked list node | the fifth set Singly linked list data structure of the check method of array and list | singly linked list data structure of the set of 6-1 check method of array and list | set 6-2 singly linked list data structure of the length of the chain table lookup (iteration and recursion) | 7 sets of singly linked list data structure of switching nodes in the list without exchanging data | 8 sets Singly linked list data structure of the inversion list | 9 sets of singly linked list data structure of merging two sorted lists | 10 sets of singly linked list data structure of the list of merge sort | 11 sets of singly linked list data structure with the size of a given set of inversion list | detection of 12 sets of singly linked list data structure and delete cycle | 13 set in the list

📣 Endnote: For more information on data structures, you can follow me: Haiyong, I hope you found this article helpful.

If you see this, thank you for reading 🙂

💌 welcomes your comments and suggestions in the comments section! 💌

If you really learn something new from this article, like it, bookmark it and share it with your friends. 🤗 and finally, don’t forget ❤ or 📑.