Reverse a Linked List
Problem Statement
Given a singly linked list, the task is to reverse the list, meaning that the last node becomes the first node, the second-to-last node becomes the second node, and so on.
Recursive Approach
The recursive approach to reversing a linked list involves breaking the problem into smaller subproblems. Here are the general steps:
- Divide the linked list into two parts: the first node (head) and the rest of the list (the linked list without the first node).
- Recursively reverse the rest of the linked list.
- After the recursion, change the next of the last node of the reversed rest to point to the first node.
- Set the next of the first node to NULL to make it the new tail.
Implementation of Recursive Approach
C++ Implementation
#include <iostream>
class Node {
public:
int data;
Node* next;
Node(int data) : data(data), next(nullptr) {}
};
Node* reverseLinkedList(Node* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
Node* restReversed = reverseLinkedList(head->next);
head->next->next = head;
head->next = nullptr;
return restReversed;
}
void printLinkedList(Node* head) {
while (head != nullptr) {
std::cout << head->data << " ";
head = head->next;
}
std::cout << std::endl;
}
int main() {
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
std::cout << "Original Linked List: ";
printLinkedList(head);
head = reverseLinkedList(head);
std::cout << "Reversed Linked List: ";
printLinkedList(head);
return 0;
}
Java Implementation
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class ReverseLinkedList {
public static Node reverseLinkedList(Node head) {
if (head == null || head.next == null) {
return head;
}
Node restReversed = reverseLinkedList(head.next);
head.next.next = head;
head.next = null;
return restReversed;
}
public static void printLinkedList(Node head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
public static void main(String[] args) {
Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
System.out.print("Original Linked List: ");
printLinkedList(head);
head = reverseLinkedList(head);
System.out.print("Reversed Linked List: ");
printLinkedList(head);
}
}
Python Implementation
class ListNode:
def __init__(self, data):
self.data = data
self.next = None
def reverseLinkedList(head):
if head is None or head.next is None:
return head
restReversed = reverseLinkedList(head.next)
head.next.next = head
head.next = None
return restReversed
def printLinkedList(head):
while head:
print(head.data, end=" ")
head = head.next
print()
# Helper function to create a linked list from a list
def createLinkedList(arr):
if not arr:
return None
head = ListNode(arr[0])
current = head
for item in arr[1:]:
current.next = ListNode(item)
current = current.next
return head
# Helper function to print a linked list
def printLinkedList(head):
while head:
print(head.data, end=" ")
head = head.next
print()
if __name__ == "__main__":
arr = [1, 2, 3, 4]
head = createLinkedList(arr)
print("Original Linked List:", end=" ")
printLinkedList(head)
head = reverseLinkedList(head)
print("Reversed Linked List:", end=" ")
printLinkedList(head)
Iterative Approach
The iterative approach to reversing a linked list involves traversing the list once and modifying the next pointers of each node to reverse the direction of the list.
Dry Run of the Iterative Approach
Let’s dry run the iterative approach on a simple example:
Original Linked List: 1 -> 2 -> 3 -> 4 -> null
- Initialize three pointers: prev = null, current = head (1st node), and next = null.
- Iterate through the linked list.
-
- In each iteration, update the next pointer of the current node to point to the previous node (reverse the link).
- Update prev to be the current node.
- Update current to be the next node (move forward).
- After the loop, update the head to be prev, which is now pointing to the new first node (4).
- The reversed linked list is now: 4 -> 3 -> 2 -> 1 -> null.
Implementation of Iterative Approach
C++ Implementation
#include <iostream>
class Node {
public:
int data;
Node* next;
Node(int data) : data(data), next(nullptr) {}
};
Node* reverseLinkedList(Node* head) {
Node* prev = nullptr;
Node* current = head;
Node* next = nullptr;
while (current != nullptr) {
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev; // New head of the reversed list
}
void printLinkedList(Node* head) {
while (head != nullptr) {
std::cout << head->data << " ";
head = head->next;
}
std::cout << std::endl;
}
int main() {
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
head->next->next->next = new Node(4);
std::cout << "Original Linked List: ";
printLinkedList(head);
head = reverseLinkedList(head);
std::cout << "Reversed Linked List: ";
printLinkedList(head);
return 0;
}
Java Implementation
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
public class ReverseLinkedList {
public static Node reverseLinkedList(Node head) {
Node prev = null;
Node current = head;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
return prev; // New head of the reversed list
}
public static void printLinkedList(Node head)
FAQs
1.What is a linked list?
A linked list is a linear data structure consisting of nodes, where each node points to the next node in the sequence. It’s used to store and manage a collection of elements.
2.Why would you want to reverse a linked list?
Reversing a linked list can be useful in various scenarios, such as when you need to process elements in a different order, search for elements from the end, or improve the efficiency of certain operations.
3.What is the difference between reversing a linked list iteratively and recursively?
The iterative approach reverses the linked list by iteratively modifying the next pointers of each node to change the direction of the list. The recursive approach divides the problem into smaller subproblems, recursively reverses the rest of the list, and then combines the results.
4.Is there a preferred approach (iterative vs. recursive) for reversing a linked list?
The choice between the iterative and recursive approaches often depends on personal preference and the specific requirements of the problem. Both approaches are valid and can achieve the same result.
5.What is the time complexity of reversing a linked list?
Both the iterative and recursive approaches have a time complexity of O(n), where n is the number of nodes in the linked list. This is because they visit each node once.
