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):
    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

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.

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.