We're sorry this tutorial wasn't helpful. Please tell us what we can do better.
Reverse a Circular Linked List
Last updated:
Hello, In this tutorial, we will see how to reverse a circular linked list.
Let's first understand what a reversed list is, as given in the example below.
Example:
Java program implementation of reverse a circular linked list
ReverseCLL.java
// Class representing a node in a circular linked list
class Node {
public int data; // Store value of the node
public Node next; // Store address of the next node
// Constructor to initialize a node
public Node(int data) {
this.data = data;
this.next = null;
}
}
public class ReverseCLL {
// Function to reverse the circular linked list
static Node reverse(Node head_ref) {
// if list is empty
if (head_ref == null)
return null;
// reverse procedure same as reversing a
// singly linked list
Node prev = null;
Node current = head_ref;
Node next;
do {
next = current.next;
current.next = prev;
prev = current;
current = next;
} while (current != (head_ref));
// adjusting the links so as to make the
// last node point to the first node
(head_ref).next = prev;
head_ref = prev;
return head_ref;
}
// Function to print circular linked list
static void printList(Node head) {
if (head == null)
return;
Node temp = head;
do {
System.out.print(temp.data + " ");
temp = temp.next;
} while (temp != head);
}
public static void main(String args[]) {
// Create a circular linked list
Node head = new Node(65);
head.next = new Node(47);
head.next.next = new Node(32);
head.next.next.next = new Node(40);
head.next.next.next.next = new Node(52);
head.next.next.next.next.next = head;
System.out.print("Original circular linked list: ");
printList(head);
head = reverse(head);
System.out.print("\nReversed circular linked list: ");
printList(head);
}
}
Time Complexity: O(n), here n represent the total number of nodes in a circular linked list.
Auxiliary Space: O(1)
Frequently Asked Questions (FAQ)
Q1. How do you reverse a circular linked list?
Reverse every next link as in a linear list, but stop when you return to the head. Finally, link the old head to the new head to close the ring:
ReverseCircular.java
static Node reverse(Node head) {
if (head == null || head.next == head) {
return head;
}
Node previous = null;
Node current = head;
do {
Node next = current.next;
current.next = previous;
previous = current;
current = next;
} while (current != head);
head.next = previous; // old head (now last) points to the new head
return previous; // previous is the new head
}
Q2. Why is the final step head.next = previous needed?
During the loop, the old head's next is set to null, because previous was null at the first step. The old head is now the last node, so it must point to the new head to keep the list circular.
Q3. What is the time and space complexity of reversing a circular list?
O(n) time, because each node is visited once, and O(1) extra space.
Q4. What are the edge cases?
An empty list stays empty.
A list with one node (pointing to itself) stays the same.
A list with two nodes ends up with the head and second node swapped but still pointing to each other.
Q5. How do you verify that a reversed circular list is correct?
Print it with a do-while loop from the new head. The values should appear in reverse order, and the traversal should return to the head after exactly n steps.
Q6. Can you reverse a circular linked list using a stack?
Yes. Push all values onto a stack, then walk the list again and overwrite each node's value with the popped value. It is easy to write but needs O(n) extra space:
ReverseWithStack.java
import java.util.ArrayDeque;
import java.util.Deque;
static void reverseValues(Node head) {
if (head == null) {
return;
}
Deque<Integer> stack = new ArrayDeque<>();
Node current = head;
do {
stack.push(current.data);
current = current.next;
} while (current != head);
do {
current.data = stack.pop();
current = current.next;
} while (current != head);
}
Q7. How do you reverse a circular doubly linked list?
Swap the prev and next references of every node, going around once, and make the old last node (head.prev before the swap) the new head.
Q8. How does reversing a circular list differ from reversing a linear list?
The loop condition changes from current != null to "until we are back at the head", and one extra link must be fixed at the end to close the ring.
Q9. If the list is tracked by a last reference, what changes after reversing?
The old head becomes the new last node, so the last reference must be updated to point to the old head.
Q10. Write a recursive Java method to reverse a circular linked list.
ReverseRecursiveCircular.java
static Node reverse(Node head) {
if (head == null || head.next == head) {
return head;
}
Node newHead = reverseFrom(head, head, null);
head.next = newHead; // close the ring
return newHead;
}
private static Node reverseFrom(Node current, Node head, Node previous) {
Node next = current.next;
current.next = previous;
if (next == head) {
return current; // the last original node is the new head
}
return reverseFrom(next, head, current);
}
