How do you Recverse a linked list using recursion?

Recursively Reversing a linked list [A simple implementation]

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

Examples:

Input : Head of following linked list 1->2->3->4->NULL Output : Linked list should be changed to, 4->3->2->1->NULL Input : Head of following linked list 1->2->3->4->5->NULL Output : Linked list should be changed to, 5->4->3->2->1->NULL Input : NULL Output : NULL Input : 1->NULL Output : 1->NULL

Reverse a linked list

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

Examples:

Input: Head of following linked list
1->2->3->4->NULL
Output: Linked list should be changed to,
4->3->2->1->NULL

Input: Head of following linked list
1->2->3->4->5->NULL
Output: Linked list should be changed to,
5->4->3->2->1->NULL

Input: NULL
Output: NULL

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

C

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88

#include #include // A Linked List Node struct Node { int data; struct Node* next; }; // Helper function to print a given linked list void printList[struct Node* head] { struct Node* ptr = head; while [ptr] { printf["%d —> ", ptr->data]; ptr = ptr->next; } printf["NULL\n"]; } // Helper function to insert a new node at the beginning of the linked list void push[struct Node** head, int data] { struct Node* newNode = [struct Node*]malloc[sizeof[struct Node]]; newNode->data = data; newNode->next = *head; *head = newNode; } // Recursive function to reverse a given linked list. It reverses the // given linked list by fixing the head pointer and then `.next` // pointers of every node in reverse order void recursiveReverse[struct Node* head, struct Node** headRef] { struct Node* first; struct Node* rest; // empty list base case if [head == NULL] { return; } first = head; // suppose first = {1, 2, 3} rest = first->next; // rest = {2, 3} // base case: the list has only one node if [rest == NULL] { // fix the head pointer here *headRef = first; return; } // recursively reverse the smaller {2, 3} case // after: rest = {3, 2} recursiveReverse[rest, headRef]; // put the first item at the end of the list rest->next = first; first->next = NULL; // [tricky step — make a drawing] } // Reverse a given linked list. The function takes a pointer // [reference] to the head pointer void reverse[struct Node** head] { recursiveReverse[*head, head]; } int main[void] { // input keys int keys[] = { 1, 2, 3, 4, 5, 6 }; int n = sizeof[keys]/sizeof[keys[0]]; struct Node* head = NULL; for [int i = n - 1; i >=0; i--] { push[&head, keys[i]]; } reverse[&head]; printList[head]; return 0; }

DownloadRun Code

Output:

6 —> 5 —> 4 —> 3 —> 2 —> 1 —> NULL

Reverse a Linked List C++ Code [Iterative and Recursive]

Many of you must be familiar with the application of a linked list in the real world and its importance. We use linked lists to maintain a directory of names, dynamic allocation of memory, and create an implementation of essentials data structures like stacks and queues, and what not?

Knowing all this in this tutorial we are going to discuss the basic understanding of a linked list, and implement and analyze how to reverse a linked list in C++. Let’s get Kraken!

How to recursively reverse a linked list

An intuition-building approach

The recursive algorithm for reversing a linked list can be very unintuitive for a lot of people. In this article, we will gradually build our intuition about this algorithm in the sections that follow.

Before discussing the recursive algorithm, it’s important for us to understand why we are able to use recursion in the first place.

Image source: //www.flickr.com/photos/torley/2361164281

Here’s the big idea. The linked list is a recursive data structure, which means we can use recursive functions to query or perform operations on it.

We can use recursive functions to query or perform operations on recursive data structures.

Reverse a Linked List using Iteration

Algorithm to reverse a linked list using iteration
We will use three node pointer "previous", "current" and "next" to keep track of previous, current and next node during linked list reversal.

• Initialize current pointer to head and previous pointer to NULL.
• Traverse linked list from head till current->next != NULL.
• In every iteration, set current->next = previous; and move all three pointers to next node.
• Return previous pointer. This is the new head pointer of reversed linked list.

#include #include /* A structure of linked list node */ struct node { int data; struct node *next; } *head; void initialize[]{ head = NULL; } /* Given a Inserts a node in front of a singly linked list. */ void insert[int num] { /* Create a new Linked List node */ struct node* newNode = [struct node*] malloc[sizeof[struct node]]; newNode->data = num; /* Next pointer of new node will point to head node of linked list */ newNode->next = head; /* make new node as new head of linked list */ head = newNode; printf["Inserted Element : %d\n", num]; } /* Reverses a given Linked List, and return the head pointer of reversed linked list */ struct node* reverseLinkedList[struct node *head] { struct node *previous, *current, *next; previous = NULL; current = head; while [current != NULL] { next = current->next; current->next = previous; previous = current; current = next; } return previous; } /* Prints a linked list from head node till tail node */ void printLinkedList[struct node *nodePtr] { while [nodePtr != NULL] { printf["%d", nodePtr->data]; nodePtr = nodePtr->next; if[nodePtr != NULL] printf["-->"]; } } int main[] { initialize[]; /* Creating a linked List*/ insert[8]; insert[3]; insert[2]; insert[7]; insert[9]; printf["\nLinked List\n"]; printLinkedList[head]; /* Reverse Linked List */ head = reverseLinkedList[head]; printf["\nReversed Linked List\n"]; printLinkedList[head]; return 0; } Output
Inserted Element : 8 Inserted Element : 3 Inserted Element : 2 Inserted Element : 7 Inserted Element : 9 Linked List 8-->3-->2-->7-->9 Reversed Linked List 9-->7-->2-->3-->8

Reverse a Linked List

Difficulty:Medium

Asked in: Microsoft, MakeMyTrip, Adobe, Amazon

Understanding the Problem: →

Given a linked list pointed by a head node as input, your task is to reverse the linked list. After the reversal, The head data should become the last data element pointing to null. This should be done by de-linking the nodes and again linking it in reverse order.

For example:

Input: 2→3→4→5→6→7→NULL

Output: 7→6→5→4→3→2→NULL

Similarly

Input: 21→32→43→54→65→76→NULL

Output: 76→65→54→43→32→21→NULL

Possible follow-up questions to ask the interviewer:

• Do we have to print the Linked List in reverse order?[Ans: No, just return the head of the reversed Linked List.]
• What if only one node is given in input?[Ans: Just output that node]

Solutions

Solution idea

The idea here is to de-link a node from its previous node and add the previous node in front of the current node. We will follow the same approach for all the node and finally our new reversed Linked List will be ready. This idea can be implemented in two ways →

• Recursive Solution
• Iterative Solution

Recursive Solution

Solution steps

• We can divide the linked list with n nodes into two parts: head and the rest of the linked list with n-1 nodes [Smaller problem].
• Recursively reverse the linked list with [n-1] nodes and return the head pointer of this part i.e. restReversedPart. After the reversal, the next node of the head will be the last node and the head will be pointing to this node.
• But for the complete reversal of the list, the head should be the last node. So, do the following operations to ensure this:

head.next.next = head head.next = NULL

• Return the head pointer of the reversed list i.e. return restReversedPart.
• Base Case: if[head == NULL || head.next == NULL] then return Null.

Pseudo-Code

ListNode reverseList[ListNode head]{ if[head == NULL || head.next == NULL] return NULL ListNode restReversedPart= reverseList[head.next] head.next.next = head head.next = NULL return restReversedPart}

Complexity Analysis

Recurrence relation: T[n] = T[n-1] + O[1]
Time Complexity = O[n], where n is the length of the Linked List
Space Complexity = O[n], for recursion stack space. [Think!]

Iterative Approach

Solution steps

• We will take three pointers named current, previous and nextNode and will initialize them.

ListNode current = head ListNode previous = NULL ListNode nextNode = NULL

• We will iterate over the linked list untill current is not equal to NULL and do the following update in every step of the iteration:

nextNode = current.next current.next = previous previous = current current = nextNode

• return previous pointer which will be the head of the reversed list.

Pseudo-Code

ListNode reverseList[ListNode head] { if[head == NULL] return NULL ListNode current = head ListNode previous = NULL ListNode nextNode = NULL while[current != NULL] { nextNode = current.next current.next = previous previous = current current = nextNode } return previous }

Complexity Analysis

Time Complexity = O[n], where n is the length of the Linked List

Space Complexity = O[1]

Critical ideas to think!

• Can we reverse a Linked List in less than O[n] time? Impossible right? What if the Linked List is doubly Linked List.
• Can we use Stack for reversing the Linked List? If Yes, what will be the Complexity?

Suggested Problems to Solve

• Reverse a Linked List from position M to N.
• Reverse a Stack.
• Reverse a Linked List in groups of given size.
• Reverse a Linked List using Stack.

Happy Coding! Enjoy Algorithms!!

AfterAcademy Data Structure And Algorithms Online Course — Admissions Open