.png)
Exchange First and Last Nodes in a Circular Linked List
Problem Statement
Given a circular linked list, write a program to exchange (swap) the first and last nodes of the list without changing the data inside the nodes.
The circular structure of the list must be maintained after the exchange.
Example
Input
Circular Linked List:
10 → 20 → 30 → 40 → back to 10
Output
40 → 20 → 30 → 10 → back to 40
Approach: Pointer Manipulation
To exchange the first and last nodes in a circular linked list:
- Identify:
- The head node
- The last node
- The second last node
- Update pointers so that:
- Last node becomes the new head
- Old head becomes the last node
- Ensure the last node points back to the new head to preserve circularity
No data swapping is performed; only pointers are updated.
Algorithm
- If the list is empty or has only one node, return.
- Initialize:
- prev = NULL
- curr = head
- Traverse the list to find the last node and its previous node.
- Set:
- prev->next = head
- curr->next = head->next
- Update:
- head->next = curr
- head = curr
- Return the updated head.
Time Complexity
- Best Case: O(1)
- Worst Case: O(n)
- Average Case: O(n)
Space Complexity
- O(1)
Edge Cases
- Empty list
- Single node list
- Two-node circular list
C Implementation
// While running this code, replace all #include "..." with #include <...>
#include "stdio.h"
#include "stdlib.h"
struct Node {
int data;
struct Node* next;
};
// Function to exchange first and last node
struct Node* exchangeFirstLast(struct Node* head) {
if (head == NULL || head->next == head)
return head;
struct Node* prev = NULL;
struct Node* curr = head;
while (curr->next != head) {
prev = curr;
curr = curr->next;
}
prev->next = head;
curr->next = head->next;
head->next = curr;
head = curr;
return head;
}
void printList(struct Node* head) {
if (head == NULL) return;
struct Node* temp = head;
do {
printf("%d -> ", temp->data);
temp = temp->next;
} while (temp != head);
printf("(back to head)\n");
}
struct Node* insertEnd(struct Node* head, int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
if (head == NULL) {
newNode->next = newNode;
return newNode;
}
struct Node* temp = head;
while (temp->next != head)
temp = temp->next;
temp->next = newNode;
newNode->next = head;
return head;
}
int main() {
struct Node* head = NULL;
head = insertEnd(head, 1);
head = insertEnd(head, 2);
head = insertEnd(head, 3);
head = insertEnd(head, 4);
printf("Original List:\n");
printList(head);
head = exchangeFirstLast(head);
printf("After Exchanging First and Last:\n");
printList(head);
return 0;
}C++ Implementation
// While running this code, replace all #include "..." with #include <...>
#include "iostream"
using namespace std"
struct Node {
int data;
Node* next;
};
// Function to exchange first and last nodes
Node* exchangeFirstLast(Node* head) {
if (head == NULL || head->next == head)
return head;
Node* prev = NULL;
Node* curr = head;
// Find last and second last node
while (curr->next != head) {
prev = curr;
curr = curr->next;
}
// Adjust pointers
prev->next = head; // second last -> old head
curr->next = head->next; // last -> second node
head->next = curr; // old head -> last
head = curr; // update head
return head;
}Java Implementation
static Node exchangeFirstLast(Node head) {
if (head == null || head.next == head)
return head;
Node prev = null;
Node curr = head;
while (curr.next != head) {
prev = curr;
curr = curr.next;
}
prev.next = head;
curr.next = head.next;
head.next = curr;
head = curr;
return head;
}
Python Implementation
def exchange_first_last(head):
if head is None or head.next == head:
return head
prev = None
curr = head
while curr.next != head:
prev = curr
curr = curr.next
prev.next = head
curr.next = head.next
head.next = curr
head = curr
return head
JavaScript Implementation
function exchangeFirstLast(head) {
if (head === null || head.next === head)
return head;
let prev = null;
let curr = head;
while (curr.next !== head) {
prev = curr;
curr = curr.next;
}
prev.next = head;
curr.next = head.next;
head.next = curr;
head = curr;
return head;
}
Output
Original List:
1 -> 2 -> 3 -> 4 -> (back to head)
After Exchanging First and Last:
4 -> 2 -> 3 -> 1 -> (back to head)Key Points to Remember
- Only pointers are exchanged, not node data
- Circularity must be preserved
- Traversal stops when the head node is reached again
- Special handling required for small lists
Conclusion
Exchanging the first and last nodes in a circular linked list is an important pointer-manipulation problem. By carefully updating the previous and next pointers, the operation can be completed efficiently in linear time and constant space without breaking the circular structure.
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.png)
.jpg)
.png)
.jpg)
.jpg)
.jpg)
