Posted on by Kalkicode
Code Circular Linked List

# Exchange first and last nodes in Circular Linked List

In the problem of exchanging the first and last nodes in a circular linked list, we are working with a circular linked list data structure. The goal is to swap the positions of the first and last nodes in the list while maintaining the circular structure.

## Problem Statement

Given a circular linked list, we need to exchange the positions of the first and last nodes. After the exchange, the first node should become the last node, and the last node should become the first node. The circular structure of the linked list should be preserved.

## Example

Consider a circular linked list with the following elements: 1 -> 3 -> 5 -> 2 -> 6 -> 7. After exchanging the first and last nodes, the list becomes: 7 -> 3 -> 5 -> 2 -> 6 -> 1.

## Idea to Solve the Problem

To exchange the first and last nodes in a circular linked list, we need to identify the following cases:

1. The linked list is empty.
2. The linked list has only one node.
3. The linked list has more than one node.

Based on these cases, we can determine how to perform the exchange of nodes while maintaining the circular structure.

## Pseudocode

Here's the pseudocode to exchange the first and last nodes in a circular linked list:

``````function swapNodes(circularLinkedList):
print "Empty linked list"
return
print "Only one element in linked list"
return

prev = temp
temp = temp.next

else:
temp = prev.next
temp.next = first.next
first.next = temp

## Algorithm Explanation

1. Check if the linked list is empty. If it is, print a message and return.
2. Check if the linked list has only one node. If it does, print a message and return.
3. Initialize `temp`, `first`, and `prev` pointers to the head of the linked list.
4. Traverse the linked list using the `temp` pointer until it reaches the last node. Keep track of the second-to-last node using the `prev` pointer.
5. If `prev` is still pointing to the head, it means there are only two nodes in the list. In this case, update the head to the second node.
6. Otherwise, exchange the links to swap the first and last nodes. Update the necessary pointers to maintain the circular structure.
7. Update the head of the linked list to point to the new first node.

## Time Complexity

The time complexity of swapping the first and last nodes in a circular linked list is O(n), where n is the number of nodes in the circular linked list. This is because we need to traverse the list to find the second-to-last node, which requires a linear scan through the list. The space complexity is O(1) as we are using only a constant amount of extra space for 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.

Categories
Relative Post