Reverse a Circular Linked List
The problem involves reversing a circular linked list in place, which means reversing the direction of pointers in the linked list nodes to change the order of elements.
Problem Statement
Given a circular linked list, the task is to reverse the linked list in place, i.e., without using additional memory, and update the connections between nodes accordingly.
Example
Consider the circular linked list: 1 -> 2 -> 3 -> 4 -> 5 -> 1. After reversing it in place, the circular linked list becomes: 5 -> 4 -> 3 -> 2 -> 1 -> 5.
Idea to Solve the Problem
To reverse a circular linked list in place, we can use three pointers: back
, curr
, and
temp
. We iterate through the linked list and reverse the direction of pointers as follows:


back
initially points to NULL.curr
points to the current node we are processing.temp
is used to keep track of the next node before reversing the link.
Pseudocode
Here's the pseudocode to reverse a circular linked list in place:
function reverse():
if head is NULL:
print "Empty linked list"
return
temp = head
back = NULL
curr = NULL
while temp is not NULL and temp.next is not head:
curr = temp
temp = temp.next
curr.next = back
back = curr
// Attach the first node's next pointer to the last node
head.next = temp
if back is not NULL:
temp.next = back
// Update the head to point to the last node (new first node)
head = temp
Algorithm Explanation
- Check if the linked list is empty. If it's empty, print "Empty linked list" and return.
- Initialize
temp
to the head of the linked list,back
to NULL, andcurr
to NULL. - Iterate through the linked list using the
temp
pointer while also checking iftemp.next
is not the head node (this prevents us from creating an infinite loop when reversing). - In each iteration, reverse the direction of the
curr
node's next pointer to point to theback
node. - Update
back
to the current node (curr
) and movetemp
to the next node. - After the loop, attach the first node's next pointer to the
temp
node (new last node). - If
back
is not NULL, update thetemp
node's next pointer to point to theback
node. - Update the
head
to point to thetemp
node, making it the new first node of the circular linked list.
Code Solution
-
1) Reverse a circular linked list in java
2) Reverse a circular linked list in c++
3) Reverse a circular linked list in c
4) Reverse a circular linked list in golang
5) Reverse a circular linked list in c#
6) Reverse a circular linked list in vb.net
7) Reverse a circular linked list in php
8) Reverse a circular linked list in node js
9) Reverse a circular linked list in python
10) Reverse a circular linked list in ruby
11) Reverse a circular linked list in scala
12) Reverse a circular linked list in swift
13) Reverse a circular linked list in kotlin
14) Reverse a circular linked list in typescript
Time Complexity
The time complexity of reversing a circular linked list in place is O(n), where n is the number of nodes in the linked list. This is because we traverse the entire linked list once to reverse the pointers.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment