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 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
Iterative Method
- Initialize three pointers prev as NULL, curr as head and next as NULL.
- Iterate trough the linked list. In loop, do following.
// Before changing next of current,
// store next node
next = curr->next// Now change next of current
// This is where actual reversing happens
curr->next = prev// Move prev and curr one step forward
prev = curr
curr = next
C++
// Iterative C++ program to reverse // a linked list #include<iostream> using namespace std; /* Link list node */struct Node { int data; struct Node* next; Node (int data) { this->data = data; next = NULL; } }; struct LinkedList { Node *head; LinkedList() { head = NULL; } /* Function to reverse the linked list */ void reverse() { // Initialize current, previous and // next pointers Node *current = head; Node *prev = NULL, *next = NULL; while (current != NULL) { // Store next next = current->next; // Reverse current node's pointer current->next = prev; // Move pointers one position ahead. prev = current; current = next; } head = prev; } /* Function to print linked list */ void print() { 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; } }; /* Driver program to test above function*/int main() { /* Start with the empty list */ LinkedList ll; ll.push(20); ll.push(4); ll.push(15); ll.push(85); cout << "Given linked list
"; ll.print(); ll.reverse(); cout << "
Reversed Linked list
"; ll.print(); return 0; } |
C
// Iterative C program to reverse a linked list #include<stdio.h> #include<stdlib.h> /* Link list node */struct Node { int data; struct Node* next; }; /* Function to reverse the linked list */static void reverse(struct Node** head_ref) { struct Node* prev = NULL; struct Node* current = *head_ref; struct Node* next = NULL; while (current != NULL) { // Store next next = current->next; // Reverse current node's pointer current->next = prev; // Move pointers one position ahead. prev = current; current = next; } *head_ref = prev; } /* Function to push a node */void push(struct Node** head_ref, int new_data) { struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } /* Function to print linked list */void printList(struct Node *head) { struct Node *temp = head; while(temp != NULL) { printf("%d ", temp->data); temp = temp->next; } } /* Driver program to test above function*/int main() { /* Start with the empty list */ struct Node* head = NULL; push(&head, 20); push(&head, 4); push(&head, 15); push(&head, 85); printf("Given linked list
"); printList(head); reverse(&head); printf("
Reversed Linked list
"); printList(head); getchar(); } |
Java
// Java program for reversing the linked list class LinkedList { static Node head; static class Node { int data; Node next; Node(int d) { data = d; next = null; } } /* Function to reverse the linked list */ Node reverse(Node node) { Node prev = null; Node current = node; Node next = null; while (current != null) { next = current.next; current.next = prev; prev = current; current = next; } node = prev; return node; } // prints content of double linked list void printList(Node node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } } public static void main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node(85); list.head.next = new Node(15); list.head.next.next = new Node(4); list.head.next.next.next = new Node(20); System.out.println("Given Linked list"); list.printList(head); head = list.reverse(head); System.out.println(""); System.out.println("Reversed linked list "); list.printList(head); } } // This code has been contributed by Mayank Jaiswal |
Python
# Python program to reverse a linked list # Time Complexity : O(n) # Space Complexity : O(1) # Node class class Node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = None class LinkedList: # Function to initialize head def __init__(self): self.head = None # Function to reverse the linked list def reverse(self): prev = None current = self.head while(current is not None): next = current.next current.next = prev prev = current current = next self.head = prev # Function to insert a new node at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Utility function to print the linked LinkedList def printList(self): temp = self.head while(temp): print temp.data, temp = temp.next # Driver program to test above functions llist = LinkedList() llist.push(20) llist.push(4) llist.push(15) llist.push(85) print "Given Linked List"llist.printList() llist.reverse() print "
Reversed Linked List"llist.printList() # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// C# program for reversing the linked list using System; class GFG { static void Main(string[] args) { LinkedList list = new LinkedList(); list.AddNode(new LinkedList.Node(85)); list.AddNode(new LinkedList.Node(15)); list.AddNode(new LinkedList.Node(4)); list.AddNode(new LinkedList.Node(20)); // List before reversal Console.WriteLine("Given linked list:"); list.PrintList(); // Reverse the list list.ReverseList(); // List after reversal Console.WriteLine("Reversed linked list:"); list.PrintList(); } } class LinkedList { Node head; public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } // function to add a new node at // the end of the list public void AddNode(Node node) { if (head == null) head = node; else { Node temp = head; while (temp.next != null) { temp = temp.next; } temp.next = node; } } // function to reverse the list public void ReverseList() { Node prev = null, current = head, next = null; while(current!=null) { next = current.next; current.next = prev; prev = current; current = next; } head = prev; } //function to print the list data public void PrintList() { Node current = head; while(current != null) { Console.Write(current.data + " "); current = current.next; } Console.WriteLine(); } } // This code is contributed by Mayank Sharma |
Output:
Given linked list 85 15 4 20 Reversed Linked list 20 4 15 85
Time Complexity: O(n)
Space Complexity: O(1)
Recursive Method:
1) Divide the list in two parts - first node and rest of the linked list. 2) Call reverse for the rest of the linked list. 3) Link rest to first. 4) Fix head pointer
void recursiveReverse(struct Node** head_ref) { struct Node* first; struct Node* rest; /* empty list */ if (*head_ref == NULL) return; /* suppose first = {1, 2, 3}, rest = {2, 3} */ first = *head_ref; rest = first->next; /* List has only one node */ if (rest == NULL) return; /* reverse the rest list and put the first element at the end */ recursiveReverse(&rest); first->next->next = first; /* tricky step -- see the diagram */ first->next = NULL; /* fix the head pointer */ *head_ref = rest; } |
Time Complexity: O(n)
Space Complexity: O(1)
A Simpler and Tail Recursive Method
Below is the implementation of this method.
C++
// A simple and tail recursive C++ program to reverse // a linked list #include<bits/stdc++.h> using namespace std; struct Node { int data; struct Node *next; }; void reverseUtil(Node *curr, Node *prev, Node **head); // This function mainly calls reverseUtil() // with prev as NULL void reverse(Node **head) { if (!head) return; reverseUtil(*head, NULL, head); } // A simple and tail recursive function to reverse // a linked list. prev is passed as NULL initially. void reverseUtil(Node *curr, Node *prev, Node **head) { /* If last node mark it head*/ if (!curr->next) { *head = curr; /* Update next to prev node */ curr->next = prev; return; } /* Save curr->next node for recursive call */ Node *next = curr->next; /* and update next ..*/ curr->next = prev; reverseUtil(next, curr, head); } // A utility function to create a new node Node *newNode(int key) { Node *temp = new Node; temp->data = key; temp->next = NULL; return temp; } // A utility function to print a linked list void printlist(Node *head) { while(head != NULL) { cout << head->data << " "; head = head->next; } cout << endl; } // Driver program to test above functions int main() { 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
"; printlist(head1); reverse(&head1); cout << "
Reversed linked list
"; printlist(head1); return 0; } |
Java
// Java program for reversing the Linked list class LinkedList { static Node head; static class Node { int data; Node next; Node(int d) { data = d; next = null; } } // A simple and tail recursive function to reverse // a linked list. prev is passed as NULL initially. Node reverseUtil(Node curr, Node prev) { /* If last node mark it head*/ if (curr.next == null) { head = curr; /* Update next to prev node */ curr.next = prev; return head; } /* Save curr->next node for recursive call */ Node next1 = curr.next; /* and update next ..*/ curr.next = prev; reverseUtil(next1, curr); return head; } // prints content of double linked list void printList(Node node) { while (node != null) { System.out.print(node.data + " "); node = node.next; } } public static void main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node(1); list.head.next = new Node(2); list.head.next.next = new Node(3); list.head.next.next.next = new Node(4); list.head.next.next.next.next = new Node(5); list.head.next.next.next.next.next = new Node(6); list.head.next.next.next.next.next.next = new Node(7); list.head.next.next.next.next.next.next.next = new Node(8); System.out.println("Original Linked list "); list.printList(head); Node res = list.reverseUtil(head, null); System.out.println(""); System.out.println(""); System.out.println("Reversed linked list "); list.printList(res); } } // This code has been contributed by Mayank Jaiswal |
Python
# Simple and tail recursive Python program to # reverse a linked list # Node class class Node: # Constructor to initialize the node object def __init__(self, data): self.data = data self.next = None class LinkedList: # Function to initialize head def __init__(self): self.head = None def reverseUtil(self, curr, prev): # If last node mark it head if curr.next is None : self.head = curr # Update next to prev node curr.next = prev return # Save curr.next node for recursive call next = curr.next # And update next curr.next = prev self.reverseUtil(next, curr) # This function mainly calls reverseUtil() # with previous as None def reverse(self): if self.head is None: return self.reverseUtil(self.head, None) # Function to insert a new node at the beginning def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node # Utility function to print the linked LinkedList def printList(self): temp = self.head while(temp): print temp.data, temp = temp.next # Driver program llist = LinkedList() llist.push(8) llist.push(7) llist.push(6) llist.push(5) llist.push(4) llist.push(3) llist.push(2) llist.push(1) print "Given linked list"llist.printList() llist.reverse() print "
Reverse linked list"llist.printList() # This code is contributed by Nikhil Kumar Singh(nickzuck_007) |
C#
// C# program for reversing the Linked list using System; public class LinkedList { Node head; public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } // A simple and tail recursive function to reverse // a linked list. prev is passed as NULL initially. Node reverseUtil(Node curr, Node prev) { /* If last node mark it head*/ if (curr.next == null) { head = curr; /* Update next to prev node */ curr.next = prev; return head; } /* Save curr->next node for recursive call */ Node next1 = curr.next; /* and update next ..*/ curr.next = prev; reverseUtil(next1, curr); return head; } // prints content of double linked list void printList(Node node) { while (node != null) { Console.Write(node.data + " "); node = node.next; } } // Driver code public static void Main(String[] args) { LinkedList list = new LinkedList(); list.head = new Node(1); list.head.next = new Node(2); list.head.next.next = new Node(3); list.head.next.next.next = new Node(4); list.head.next.next.next.next = new Node(5); list.head.next.next.next.next.next = new Node(6); list.head.next.next.next.next.next.next = new Node(7); list.head.next.next.next.next.next.next.next = new Node(8); Console.WriteLine("Original Linked list "); list.printList(list.head); Node res = list.reverseUtil(list.head, null); Console.WriteLine(""); Console.WriteLine(""); Console.WriteLine("Reversed linked list "); list.printList(res); } } // This code contributed by Rajput-Ji |
Output:
Given linked list 1 2 3 4 5 6 7 8 Reversed linked list 8 7 6 5 4 3 2 1
Thanks to Gaurav Ahirwar for suggesting this solution.
Recursively Reversing a linked list (A simple implementation)
Iteratively Reverse a linked list using only 2 pointers (An Interesting Method)
References:
http://cslibrary.stanford.edu/105/LinkedListProblems.pdf
leave a comment
0 Comments