|
|
// Helper function to print a given linked list void printList[Node* head] cout 3 —> 2 —> 1 —> nullptr
|
|
// Helper function to print a given linked list public static void printList[Node head] System.out.print[ptr.data + " —> "]; 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]; // 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] first = head; // suppose first = {1, 2, 3} rest = first.next; // rest = {2, 3} // base case: the list has only one node // fix the head pointer here // recursively reverse the smaller {2, 3} case headRef = reverse[rest, headRef]; // put the first item at the end of the list first.next = null; // [tricky step — make a drawing] // Reverse a given linked list. The function takes a reference to public static Node reverse[Node head] { return reverse[head, head]; public static void main[String[] args] int[] keys = { 1, 2, 3, 4, 5, 6 }; for [int i = keys.length - 1; i >=0; i--] { head = push[head, keys[i]]; |
Download Run Code
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 1 —> null
|
|
def __init__[self, data, next=None]: # Function to print a given linked list print[ptr.data, end=' —> '] # 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]: first = head # suppose first = [1, 2, 3] rest = first.next # rest = [2, 3] # base case: list has only one node # fix the head pointer here # recursively reverse the smaller {2, 3} case headRef = reverse[rest, headRef] # put the first item at the end of the list first.next = None # [tricky step — make a drawing] # Reverse a given linked list return reverse[head, head] if __name__ == '__main__': for i in reversed[range[6]]: |
Download Run Code
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:
|
|
// Helper function to print a given linked list void printList[struct Node* head] printf["%d —> ", ptr->data]; // 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]]; // 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] first = *head; // suppose first = {1, 2, 3} rest = first->next; // rest = {2, 3} reverse[&rest]; // recursively reverse the smaller {2, 3} case 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 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--] { |
Download Run Code
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 1 —> NULL
|
|
// Helper function to print a given linked list
void printList[Node* head] cout 5 —> 4 —> 3 —> 2 —> 1 —> nullptr
|
|
// 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]; // Helper function to print a given linked list public static void printList[Node head] System.out.print[ptr.data + " —> "]; 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] first = head; // suppose first = {1, 2, 3} rest = first.next; // rest = {2, 3} rest = reverse[rest]; // recursively reverse the smaller {2, 3} case 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 public static void main[String[] args] int[] keys = { 1, 2, 3, 4, 5, 6 }; for [int i = keys.length - 1; i >=0; i--] { head = push[head, keys[i]]; |
Download Run Code
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 1 —> null
|
|
def __init__[self, data, next=None]: # Function to print a given linked list print[ptr.data, end=' —> '] # 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 first = head # suppose first = [1, 2, 3] rest = first.next # rest = [2, 3] rest = reverse[rest] # recursively reverse the smaller {2, 3} case 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 if __name__ == '__main__': for i in reversed[range[6]]: |
Download Run Code
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:
|
|
// Helper function to print a given linked list void printList[struct Node* head] printf["%d —> ", ptr->data]; // 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]]; // 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 // 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] // 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 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--] { |
Download Run Code
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 1 —> NULL
|
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 #include 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 =0; i--] { push[head, keys[i]]; } reverse[head]; printList[head]; return 0; } |
Download Run Code
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 1 —> nullptr
|
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]; } } |
Download Run Code
Output:
6 —> 5 —> 4 —> 3 —> 2 —> 1 —> null
|
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] |
Download Run Code
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.
Video liên quan
| |