Reverse a Linked List – Recursive Solution | C, C++, Java, and Python
This post will reverse the singly linked list using recursion in C, C++, Java, and Python.
For example,
Input: 1 —> 2 —> 3 —> 4 —> 5 —> null
Output: 5 —> 4 —> 3 —> 2 —> 1 —> null
Output: 5 —> 4 —> 3 —> 2 —> 1 —> null
We have already discussed an iterative solution to reverse the linked list in the previous post. In this post, we will cover the recursive implementation of it.
Following is the simple recursive implementation that works by fixing .next pointers of the list’s nodes and finally the head pointer. Probably the hardest part is accepting the concept that the reverse(&rest, head) does reverse the rest. Then, there’s a trick to getting the one front node at the end of the list. We recommend making a drawing to see how the trick works.
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 <stdio.h> #include <stdlib.h> // 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; } |
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 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 <iostream> #include <vector> using namespace std; // A Linked List Node struct Node { int data; Node* next; }; // Helper function to print a given linked list void printList(Node* head) { Node* ptr = head; while (ptr) { cout << ptr->data << " —> "; ptr = ptr->next; } cout << "nullptr" << endl; } // Helper function to insert a new node at the beginning of the linked list void push(Node* &headRef, int data) { Node* newNode = new Node(); newNode->data = data; newNode->next = headRef; headRef = 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(Node* head, Node* &headRef) { Node* first; Node* rest; // empty list base case if (head == nullptr) { return; } first = head; // suppose first = {1, 2, 3} rest = first->next; // rest = {2, 3} // base case: the list has only one node if (rest == nullptr) { // 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 = nullptr; // (tricky step — make a drawing) } // Reverse a given linked list. The function takes a pointer // (reference) to the head pointer void reverse(Node* &headRef) { recursiveReverse(headRef, headRef); } int main() { // input keys vector<int> keys = { 1, 2, 3, 4, 5, 6 }; Node* head = nullptr; for (int i = keys.size() - 1; i >=0; i--) { push(head, keys[i]); } reverse(head); printList(head); return 0; } |
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 1 —> nullptr
Java
|
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 |
// A Linked List Node class Node { int data; Node next; Node(int data) { this.data = data; } } class Main { // Helper function to print a given linked list public static void printList(Node head) { Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " —> "); ptr = ptr.next; } System.out.println("null"); } // Helper function to insert a new node at the beginning of the linked list public static Node push(Node head, int data) { Node node = new Node(data); node.next = head; return node; } // 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 public static Node reverse(Node head, Node headRef) { Node first, rest; // empty list base case if (head == null) { return headRef; } 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 headRef; } // recursively reverse the smaller {2, 3} case // after: rest = {3, 2} headRef = reverse(rest, headRef); // put the first item at the end of the list rest.next = first; first.next = null; // (tricky step — make a drawing) return headRef; } // Reverse a given linked list. The function takes a reference to // the head node public static Node reverse(Node head) { return reverse(head, head); } public static void main(String[] args) { // input keys int[] keys = { 1, 2, 3, 4, 5, 6 }; Node head = null; for (int i = keys.length - 1; i >=0; i--) { head = push(head, keys[i]); } head = reverse(head); printList(head); } } |
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 1 —> null
Python
|
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 |
# A Linked List Node class Node: def __init__(self, data, next=None): self.data = data self.next = next # Function to print a given linked list def printList(head): ptr = head while ptr: print(ptr.data, end=' —> ') ptr = ptr.next print('None') # 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 def reverse(head, headRef): # empty list base case if head is None: return headRef first = head # suppose first = [1, 2, 3] rest = first.next # rest = [2, 3] # base case: list has only one node if rest is None: # fix the head pointer here headRef = first return headRef # recursively reverse the smaller {2, 3} case # after: rest = [3, 2] headRef = reverse(rest, headRef) # put the first item at the end of the list rest.next = first first.next = None # (tricky step — make a drawing) return headRef # Reverse a given linked list def reverseList(head): return reverse(head, head) if __name__ == '__main__': head = None for i in reversed(range(6)): head = Node(i + 1, head) head = reverseList(head) printList(head) |
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 1 —> None
We can also solve this problem by passing only reference to the head pointer to the function, as demonstrated below:
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 |
#include <stdio.h> #include <stdlib.h> // 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 linked list. It reverses the given // linked list by fixing the head pointer and then `.next` pointers // of every node in reverse order. void reverse(struct Node** head) { 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} // empty rest base case if (rest == NULL) { return; } reverse(&rest); // recursively reverse the smaller {2, 3} case // after: rest = {3, 2} first->next->next = first; // put the first item at the end of the list first->next = NULL; // (tricky step — make a drawing) *head = rest; // fix the head pointer } 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; } |
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 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 |
#include <iostream> #include <vector> using namespace std; // A Linked List Node struct Node { int data; Node* next; }; // Helper function to print a given linked list void printList(Node* head) { Node* ptr = head; while (ptr) { cout << ptr->data << " —> "; ptr = ptr->next; } cout << "nullptr" << endl; } // Helper function to insert a new node at the beginning of the linked list void push(Node* &headRef, int data) { Node* newNode = new Node(); newNode->data = data; newNode->next = headRef; headRef = newNode; } // Recursive function to reverse a linked list. It reverses the given // linked list by fixing the head pointer and then `.next` pointers // of every node in reverse order. // The function takes a reference to the head pointer void reverse(Node* &headRef) { Node* first; Node* rest; // empty list base case if (headRef == nullptr) { return; } first = headRef; // suppose first = {1, 2, 3} rest = first->next; // rest = {2, 3} // empty rest base case if (rest == nullptr) { return; } reverse(rest); // recursively reverse the smaller {2, 3} case // after: rest = {3, 2} first->next->next = first; // put the first item at the end of the list first->next = nullptr; // (tricky step — make a drawing) headRef = rest; // fix the head pointer } int main() { // input keys vector<int> keys = { 1, 2, 3, 4, 5, 6 }; Node* head = nullptr; for (int i = keys.size() - 1; i >=0; i--) { push(head, keys[i]); } reverse(head); printList(head); return 0; } |
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 1 —> nullptr
Java
|
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 |
// A Linked List Node class Node { int data; Node next; Node(int data) { this.data = data; } } class Main { // Helper function to insert a new node at the beginning of the linked list public static Node push(Node head, int data) { Node node = new Node(data); node.next = head; return node; } // Helper function to print a given linked list public static void printList(Node head) { Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " —> "); ptr = ptr.next; } System.out.println("null"); } // Recursive function to reverse a linked list. // It reverses the given linked list by fixing the head pointer and // then `.next` pointers of every node in reverse order public static Node reverse(Node head) { Node first, rest; // empty list base case if (head == null) { return head; } first = head; // suppose first = {1, 2, 3} rest = first.next; // rest = {2, 3} // empty rest base case if (rest == null) { return head; } rest = reverse(rest); // recursively reverse the smaller {2, 3} case // after: rest = {3, 2} first.next.next = first; // put the first item at the end of the list first.next = null; // (tricky step — make a drawing) head = rest; // fix the head pointer return head; } public static void main(String[] args) { // input keys int[] keys = { 1, 2, 3, 4, 5, 6 }; Node head = null; for (int i = keys.length - 1; i >=0; i--) { head = push(head, keys[i]); } head = reverse(head); printList(head); } } |
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 1 —> null
Python
|
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 |
# A Linked List Node class Node: def __init__(self, data, next=None): self.data = data self.next = next # Function to print a given linked list def printList(head): ptr = head while ptr: print(ptr.data, end=' —> ') ptr = ptr.next print('None') # Recursive function to reverse a linked list. # It reverses the given linked list by fixing the head pointer and # then `.next` pointers of every node in reverse order def reverse(head): # empty list base case if head is None: return head first = head # suppose first = [1, 2, 3] rest = first.next # rest = [2, 3] # empty rest base case if rest is None: return head rest = reverse(rest) # recursively reverse the smaller {2, 3} case # after: rest = [3, 2] first.next.next = first # put the first item at the end of the list first.next = None # (tricky step — make a drawing) head = rest # fix the head pointer return head if __name__ == '__main__': head = None for i in reversed(range(6)): head = Node(i + 1, head) head = reverse(head) printList(head) |
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 1 —> None
We can simplify the above code by passing previous node information to the function. Following is a simple recursive implementation of it in C, C++, Java, and Python:
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 |
#include <stdio.h> #include <stdlib.h> // 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 reverse(struct Node* curr, struct Node* prev, struct Node** head) { // base case: end of the list reached if (curr == NULL) { // fix head pointer *head = prev; return; } // recur for the next node and pass the current node as a previous node reverse(curr->next, curr, head); // fix current node (nodes following it are already fixed) curr->next = prev; } // Reverse a given linked list. The function takes a pointer // (reference) to the head pointer void Reverse(struct Node** head) { reverse (*head, NULL, 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; } |
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 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 |
#include <iostream> #include <vector> using namespace std; // A Linked List Node struct Node { int data; Node* next; }; // Helper function to print a given linked list void printList(Node* head) { Node* ptr = head; while (ptr) { cout << ptr->data << " —> "; ptr = ptr->next; } cout << "nullptr" << endl; } // Helper function to insert a new node at the beginning of the linked list void push(Node* &headRef, int data) { Node* newNode = new Node(); newNode->data = data; newNode->next = headRef; headRef = 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 reverse(Node* curr, Node* prev, Node* &headRef) { // base case: end of the list reached if (curr == nullptr) { // fix head pointer headRef = prev; return; } // recur for the next node and pass the current node as a previous node reverse(curr->next, curr, headRef); // fix current node (nodes following it are already fixed) curr->next = prev; } // The function to reverse a given linked list which takes a // reference to the head pointer void reverse(Node* &headRef) { reverse (headRef, nullptr, headRef); } int main() { // input keys vector<int> keys = { 1, 2, 3, 4, 5, 6 }; Node* head = nullptr; for (int i = keys.size() - 1; i >=0; i--) { push(head, keys[i]); } reverse(head); printList(head); return 0; } |
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 1 —> nullptr
Java
|
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 |
// A Linked List Node class Node { int data; Node next; Node(int data) { this.data = data; } } class Main { // Helper function to print a given linked list public static void printList(Node head) { Node ptr = head; while (ptr != null) { System.out.print(ptr.data + " —> "); ptr = ptr.next; } System.out.println("null"); } // Helper function to insert a new node at the beginning of the linked list public static Node push(Node head, int data) { Node node = new Node(data); node.next = head; return node; } // 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 public static Node reverse(Node curr, Node prev, Node head) { // base case: end of the list reached if (curr == null) { // fix head pointer head = prev; return head; } // recur for the next node and pass the current node as a previous node head = reverse(curr.next, curr, head); // fix current node (nodes following it are already fixed) curr.next = prev; return head; } // The function to reverse a given linked list which takes a // reference to the head node public static Node reverse(Node head) { return reverse (head, null, head); } public static void main(String[] args) { // input keys int[] keys = { 1, 2, 3, 4, 5, 6 }; Node head = null; for (int i = keys.length - 1; i >=0; i--) { head = push(head, keys[i]); } head = reverse(head); printList(head); } } |
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 1 —> null
Python
|
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 |
# A Linked List Node class Node: def __init__(self, data, next=None): self.data = data self.next = next # Function to print a given linked list def printList(head): ptr = head while ptr: print(ptr.data, end=' —> ') ptr = ptr.next print('None') # 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 def reverse(curr, prev, head): # base case: end of the list reached if curr is None: # fix head pointer head = prev return head # recur for the next node and pass the current node as a previous node head = reverse(curr.next, curr, head) # fix current node (nodes following it are already fixed) curr.next = prev return head # The function to reverse a given linked list def reverseList(head): return reverse(head, None, head) if __name__ == '__main__': head = None for i in reversed(range(6)): head = Node(i + 1, head) head = reverseList(head) printList(head) |
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 1 —> None
The time complexity of the above recursive solutions is O(n), where n is the length of the linked list. The solution is probably not appropriate for production code since it uses stack space proportionate to the lists’ lengths. Still, it provides good learning on how recursion works.
Source: http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)