Singly linked list data structure of the inversion list | 9 sets

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

Given a pointer to a list head node, the task is to reverse the list. We need to reverse the list by changing the links between the nodes.

Example:

Input: head of the following list 1->2->3->4->NULL Output: The list should be changed to 4->3->2->1->NULL

Input: the following list of head 1 – > 2 – > 3 – > 4 – > 5 – > NULL output: list should be changed to 5 – > 4 – > 3 – > 1 – > 2 – > NULL

Input: NULL Output: NULL Input: 1->NULL Output: 1->NULL

1. Initialize three Pointers prev to NULL, curr to head, and next to NULL.

2. Walk through the linked list. In the loop, do the following. // Before changing the current next one, Store the next node next = curr->next // Now change the current next node this is where the actual reversal happens curr->next = prev // Move prev and curr one step forward prev = curr curr = next

#include <iostream>
using namespace std;

struct Node {
	int data;
	struct Node* next;
	Node(int data)
	{
		this->data = data;
		next = NULL; }};struct LinkedList {
	Node* head;
	LinkedList() { head = NULL; }

	void reverse(a)
	{
		Node* current = head;
		Node *prev = NULL, *next = NULL;

		while(current ! =NULL) {
			next = current->next;
			current->next = prev;
			prev = current;
			current = next;
		}
		head = prev;
	}

	void print(a)
	{
		struct Node* temp = head;
		while(temp ! =NULL) {
			cout << temp->data << ""; temp = temp->next; }}void push(int data)
	{
		Node* temp = new Node(data); temp->next = head; head = temp; }};int main(a)
{
	LinkedList ll;
	ll.push(20);
	ll.push(4);
	ll.push(15);
	ll.push(85);

	cout << "Given linked list\n";
	ll.print(a); ll.reverse(a); cout <<"\nReversed Linked list \n";
	ll.print(a);return 0;
}
Copy the code

Output:

Given linked list
85 15 4 20 
Reversed Linked list 
20 4 15 85
Copy the code

Time complexity: O(n) Space complexity: O(1) recursive method:

   1) split the list into two parts - the first node and the rest of the list.2Reverse is called for the rest of the list.3) link the break to the first one.4) fixed the header pointerCopy the code

#include <iostream>
using namespace std;

struct Node {
	int data;
	struct Node* next;
	Node(int data)
	{
		this->data = data;
		next = NULL; }};struct LinkedList {
	Node* head;
	LinkedList()
	{
		head = NULL;
	}

	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 print(a)
	{
		struct Node* temp = head;
		while(temp ! =NULL) {
			cout << temp->data << ""; temp = temp->next; }}void push(int data)
	{
		Node* temp = new Node(data); temp->next = head; head = temp; }};int main(a)
{
	LinkedList ll;
	ll.push(20);
	ll.push(4);
	ll.push(15);
	ll.push(85);

	cout << "Given linked list\n";
	ll.print(a); ll.head = ll.reverse(ll.head);

	cout << "\nReversed Linked list \n";
	ll.print(a);return 0;
}
Copy the code

Output:

Given linked list
85 15 4 20 
Reversed Linked list
20 4 15 85
Copy the code

Time complexity: O(n) Space complexity: O(1)

A simpler approach to tail recursion

The following is an implementation of this method.

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

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

void reverseUtil(Node* curr, Node* prev, Node** head);

void reverse(Node** head)
{
	if(! head)return;
	reverseUtil(*head, NULL, head);
}

void reverseUtil(Node* curr, Node* prev, Node** head)
{
	if(! curr->next) { *head = curr; curr->next = prev;return;
	}

	Node* next = curr->next;

	curr->next = prev;

	reverseUtil(next, curr, head);
}

Node* newNode(int key)
{
	Node* temp = new Node;
	temp->data = key;
	temp->next = NULL;
	return temp;
}

void printlist(Node* head)
{
	while(head ! =NULL) {
		cout << head->data << "";
		head = head->next;
	}
	cout << endl;
}

int main(a)
{
	Node* head1 = newNode(1);
	head1->next = newNode(2);
	head1->next->next = newNode(3);
	head1->next->next->next = newNode(4);
	head1->next->next->next->next = newNode(5);
	head1->next->next->next->next->next = newNode(6);
	head1->next->next->next->next->next->next = newNode(7);
	head1->next->next->next->next->next->next->next
		= newNode(8);
	cout << "Given linked list\n";
	printlist(head1);
	reverse(&head1);
	cout << "\nReversed linked list\n";
	printlist(head1);
	return 0;
}
Copy the code

The output

Given linked list
1 2 3 4 5 6 7 8 

Reversed linked list
8 7 6 5 4 3 2 1
Copy the code

Using stack:

• Store nodes (values and addresses) on the stack until all values are entered.
• When all entries are complete, update the Head pointer to the last location (that is, the last value).
• Start popping nodes (values and addresses) and storing them in the same order until the stack is empty.
• Update the next pointer on the last Node in the stack to NULL.

Here is an implementation of the above method:

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

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

void reverseLL(Node** head)
{
	stack<Node*> s;
	Node* temp = *head;
	while(temp->next ! =NULL)
	{
		
		// Push all the nodes
		// in to stack
		s.push(temp);
		temp = temp->next;
	}
	*head = temp;

	while(! s.empty())
	{
		temp->next = s.top(a); s.pop(a); temp = temp->next; } temp->next =NULL;
}

void printlist(Node* temp)
{
	while(temp ! =NULL)
	{
		cout << temp->data << ""; temp = temp->next; }}void insert_back(Node** head, int value)
{

	Node* temp = new Node(a); temp->data = value; temp->next =NULL;

	if (*head == NULL)
	{
	*head = temp;
	return;
	}
	else
	{
	Node* last_node = *head;
	while(last_node->next ! =NULL)
	{
		last_node = last_node->next;
	}
	last_node->next = temp;
	return; }}int main(a)
{
	Node* head = NULL;

	insert_back(&head, 1);
	insert_back(&head, 2);
	insert_back(&head, 3);
	insert_back(&head, 4);
	cout << "Given linked list\n";
	printlist(head);
	reverseLL(&head);
	cout << "\nReversed linked list\n";
	printlist(head);
	return 0; } ** outputs ** ' 'C++ Given linked list1 2 3 4 
Reversed linked list
4 3 2 1 
Copy the code

Using arrays:

1. Create a linked list. 2. Then, do a count(head) function to count the nodes. 3. Initialize an array with the count size. 4. And start a while(p->next! =NULL) loops and stores all nodes’ data into an array. 5. Then print the array from the last index to the first.

#include <iostream>
#include<cstdlib>
using namespace std;

typedef struct node
{
int val;
struct node* next;
}node;

node* head=NULL;

int count(node* head) 
{
node* p=head;
int k=1;
while(p! =NULL)
{
	p=p->next;
	k++;
}
return k;
}

node *ll_reverse(node* head) 
{
node* p=head;
long int i=count(head),j=1;
long int arr[i];
while(i && p! =NULL)
{
	arr[j++]=p->val;
	p=p->next;
	i--;
}
j--;
while(j) 
{
	cout<<arr[j--]<<"";
}

return head;
}

node* insert_end(node* head,int data) 
{
node* q=head,*p=(node*)malloc(sizeof(node));
p->val=data;
while(q->next! =NULL)
{
	q=q->next;
}
q->next=p;
p->next=NULL;
return head;
}

node *create_ll(node* head,int data) 
{
node* p=(node*)malloc(sizeof(node));
p->val=data;
if(head==NULL)
{
	head=p;
	p->next=NULL;
	return head;
}
else
{
	head=insert_end(head,data);
	returnhead; }}int main(a)
{
int i=5,j=1;
while(i--)
{
	head=create_ll(head,j++);
}
head=ll_reverse(head);
	return 0;
}
Copy the code

Input:1->2->3->4->5Output:5->4->3->2->1
Copy the code

Time complexity: O(n) Space complexity: O(n)

🥇 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

📣 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 📑.