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:
- The linked list is empty.
- The linked list has only one node.
- 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):
if circularLinkedList.head is NULL:
print "Empty linked list"
return
else if circularLinkedList.head.next is circularLinkedList.head:
print "Only one element in linked list"
return
temp = circularLinkedList.head
first = circularLinkedList.head
prev = circularLinkedList.head
while temp.next is not circularLinkedList.head:
prev = temp
temp = temp.next
if prev is circularLinkedList.head:
circularLinkedList.head = prev.next
else:
temp = prev.next
temp.next = first.next
prev.next = circularLinkedList.head
first.next = temp
circularLinkedList.head = temp
Algorithm Explanation
- Check if the linked list is empty. If it is, print a message and return.
- Check if the linked list has only one node. If it does, print a message and return.
- Initialize
temp
,first
, andprev
pointers to the head of the linked list. - Traverse the linked list using the
temp
pointer until it reaches the last node. Keep track of the second-to-last node using theprev
pointer. - 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. - Otherwise, exchange the links to swap the first and last nodes. Update the necessary pointers to maintain the circular structure.
- Update the head of the linked list to point to the new first node.
Program List
-
1) Swap first and last element of circular linked list in c++
2) Swap first and last element of circular linked list in java
3) Swap first and last element of circular linked list in c
4) Swap first and last element of circular linked list in golang
5) Swap first and last element of circular linked list in c#
6) Swap first and last element of circular linked list in vb.net
7) Swap first and last element of circular linked list in php
8) Swap first and last element of circular linked list in node js
9) Swap first and last element of circular linked list in typescript
10) Swap first and last element of circular linked list in python
11) Swap first and last element of circular linked list in ruby
12) Swap first and last element of circular linked list in scala
13) Swap first and last element of circular linked list in swift
14) Swap first and last element of circular linked list in kotlin
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.
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