Skip to main content

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:

Before reverse After reverse
  1. back initially points to NULL.
  2. curr points to the current node we are processing.
  3. 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

  1. Check if the linked list is empty. If it's empty, print "Empty linked list" and return.
  2. Initialize temp to the head of the linked list, back to NULL, and curr to NULL.
  3. Iterate through the linked list using the temp pointer while also checking if temp.next is not the head node (this prevents us from creating an infinite loop when reversing).
  4. In each iteration, reverse the direction of the curr node's next pointer to point to the back node.
  5. Update back to the current node (curr) and move temp to the next node.
  6. After the loop, attach the first node's next pointer to the temp node (new last node).
  7. If back is not NULL, update the temp node's next pointer to point to the back node.
  8. Update the head to point to the temp node, making it the new first node of the circular linked list.

Code Solution

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.





Comment

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