WikiGalaxy
Reverse a Circular Linked List
Concept Explanation:
A circular linked list is a linked list where all nodes are connected in a cycle. Reversing a circular linked list requires reversing the direction of all links in the list and updating the head pointer to the last node.
// Step 1: Diagram of Initial Circular Linked List
// [Head] -> [Data | Next] -> [Data | Next] -> [Data | Next] -> [Head]
//
// Step 2: Reverse the Links
// [Head] <- [Data | Prev] <- [Data | Prev] <- [Data | Prev] <- [Head]
//
// Step 3: Update Head Pointer
// New Head: Last Node in Original List
class Node {
int data;
Node next;
Node(int d) { data = d; next = this; }
}
class CircularLinkedList {
Node head;
void reverse() {
if (head == null || head.next == head) return;
Node prev = null, current = head, next;
do {
next = current.next;
current.next = prev;
prev = current;
current = next;
} while (current != head);
head.next = prev;
head = prev;
}
}
Detailed Explanation of Code:
The function `reverse()` modifies the `next` pointers of each node to point to the previous node, effectively reversing the list. The loop continues until it reaches the original head again, ensuring all nodes are reversed. Finally, the head is updated to the last node processed.
Console Output:
Circular Linked List Reversed
Example 1: Single Node
Scenario:
Reversing a circular linked list with a single node should result in the same list since there are no links to reverse.
// Initial List: [Head] -> [Data | Next] -> [Head]
// Reversed List: [Head] -> [Data | Next] -> [Head]
Example 2: Two Nodes
Scenario:
Reversing a list with two nodes involves swapping the links between them.
// Initial List: [Head] -> [Node1 | Next] -> [Node2 | Head]
// Reversed List: [Head] -> [Node2 | Next] -> [Node1 | Head]
Example 3: Three Nodes
Scenario:
In a list with three nodes, each link is reversed to point to the previous node, and the head is updated to the last node.
// Initial List: [Head] -> [Node1 | Next] -> [Node2 | Next] -> [Node3 | Head]
// Reversed List: [Head] -> [Node3 | Next] -> [Node2 | Next] -> [Node1 | Head]
Example 4: Four Nodes
Scenario:
With four nodes, the reversal process is similar, ensuring each node points to its predecessor and updating the head.
// Initial List: [Head] -> [Node1 | Next] -> [Node2 | Next] -> [Node3 | Next] -> [Node4 | Head]
// Reversed List: [Head] -> [Node4 | Next] -> [Node3 | Next] -> [Node2 | Next] -> [Node1 | Head]
Example 5: Five Nodes
Scenario:
Reversing a list with five nodes demonstrates the scalability of the reversal algorithm, ensuring all links are correctly reversed.
// Initial List: [Head] -> [Node1 | Next] -> [Node2 | Next] -> [Node3 | Next] -> [Node4 | Next] -> [Node5 | Head]
// Reversed List: [Head] -> [Node5 | Next] -> [Node4 | Next] -> [Node3 | Next] -> [Node2 | Next] -> [Node1 | Head]
