Linked List: Given a circular linked list, exchange first and last node

Problem Statement:

Given a circular linked list, exchange first and last node

Example:

Before:

1 -> 2 -> 3 -> 4 -> 5
^                   ^
| - - - - - - - - - |


After:

5 -> 2 -> 3 -> 4 -> 1
^                   ^
| - - - - - - - - - |

Solution Explanation:

By changing links of first and last node.

Find the pointer to the previous to the last node.

Change the next links so that last and first nodes are swapped

Time Complexity: O(1)
Space Complexity: O(1)

Code Solution

#include <iostream> 
using namespace std;

class Node 
{ 
    public:
    int data; 
    Node *next;

    Node (int new_value)
    {
        data = new_value;
        next = nullptr;
    }
}; 

void print_list(Node *head) 
{ 
    Node *curr = head; 
    if(head != nullptr) 
    { 
        do 
        { 
        cout << curr->data << " "; 
        curr = curr->next; 
        } while(curr != head); 

      	cout << endl; 
    } 
} 

Node* solution(Node* head)
{
    if (head->next->next == head) 
    {
        head = head->next;
        return head;
    }
 
    Node* p = head;
    while (p->next->next != head)
        p = p->next;
 
    p->next->next = head->next;
    head->next = p->next;
    p->next = head;
    head = head->next;
 
    return head;
}

int main() 
{ 
    
    Node *head = new Node(1); 

    // Created linked list will be 1 -> 2 -> 3 -> 4 -> 5
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);
    head->next->next->next->next->next = head;
    print_list(head);
    head = solution(head);
    print_list(head);
    
    return 0; 
} 

Output

1 2 3 4 5 
5 2 3 4 1