# Exchange first and last nodes in Circular Linked List

Given a Circular linked list exchange the first and the last node. The task should be done with only one extra node, you can not declare more than one extra node and also you are not allowed to declare any other temporary variable.
Note: Extra node means need of a node to traverse a list.

Examples:

```Input : 5 4 3 2 1
Output : 1 4 3 2 5

Input  : 6 1 2 3 4 5 6 7 8 9
Output : 9 1 2 3 4 5 6 7 8 6
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

We first find pointer to previous of last node. Let this node be p. Now we change next links so that the last and first nodes are swapped.

## C++

 `// CPP program to exchange first and  ` `// last node in circular linked list ` `#include ` `using` `namespace` `std; ` ` `  `struct` `Node ` `{ ` `    ``int` `data; ` `    ``struct` `Node *next; ` `}; ` ` `  `struct` `Node *addToEmpty(``struct` `Node *head, ``int` `data) ` `{ ` `    ``// This function is only for empty list ` `    ``if` `(head != NULL) ` `    ``return` `head; ` ` `  `    ``// Creating a node dynamically. ` `    ``struct` `Node *temp =  ` `        ``(``struct` `Node*)``malloc``(``sizeof``(``struct` `Node)); ` ` `  `    ``// Assigning the data. ` `    ``temp -> data = data; ` `    ``head = temp; ` ` `  `    ``// Creating the link. ` `    ``head -> next = head; ` ` `  `    ``return` `head; ` `} ` ` `  `struct` `Node *addBegin(``struct` `Node *head, ``int` `data) ` `{ ` `    ``if` `(head == NULL) ` `        ``return` `addToEmpty(head, data); ` ` `  `    ``struct` `Node *temp = ` `        ``(``struct` `Node *)``malloc``(``sizeof``(``struct` `Node)); ` ` `  `    ``temp -> data = data; ` `    ``temp -> next = head -> next; ` `    ``head -> next = temp; ` ` `  `    ``return` `head; ` `} ` ` `  `/* function for traversing the list */` `void` `traverse(``struct` `Node *head) ` `{ ` `    ``struct` `Node *p; ` ` `  `    ``// If list is empty, return. ` `    ``if` `(head == NULL) ` `    ``{ ` `        ``cout << ``"List is empty."` `<< endl; ` `        ``return``; ` `    ``} ` ` `  `    ``// Pointing to first Node of the list. ` `    ``p = head; ` ` `  `    ``// Traversing the list. ` `    ``do` `    ``{ ` `        ``cout << p -> data << ``" "``; ` `        ``p = p -> next; ` ` `  `    ``} ``while``(p != head); ` `} ` ` `  `/* Function to exchange first and last node*/` `struct` `Node *exchangeNodes(``struct` `Node *head) ` `{ ` `    ``// Find pointer to previous of last node ` `    ``struct` `Node *p = head; ` `    ``while` `(p->next->next != head) ` `       ``p = p->next; ` `     `  `    ``/* Exchange first and last nodes using ` `       ``head and p */` `    ``p->next->next = head->next; ` `    ``head->next = p->next; ` `    ``p->next = head; ` `    ``head = head->next; ` ` `  `    ``return` `head; ` `} ` ` `  `// Driven Program ` `int` `main() ` `{ ` `    ``int` `i; ` `    ``struct` `Node *head = NULL; ` `    ``head = addToEmpty(head, 6); ` `     `  `    ``for` `(i = 5; i > 0; i--) ` `    ``head = addBegin(head, i); ` `    ``cout << ``"List Before: "``; ` `    ``traverse(head); ` `    ``cout << endl; ` `     `  `    ``cout << ``"List After: "``; ` `    ``head = exchangeNodes(head); ` `    ``traverse(head); ` ` `  `    ``return` `0; ` `} `

## Java

 `// Java program to exchange  ` `// first and last node in  ` `// circular linked list ` `class` `GFG ` `{ ` ` `  `static` `class` `Node ` `{ ` `    ``int` `data; ` `    ``Node next; ` `}; ` ` `  `static` `Node addToEmpty(Node head,  ` `                       ``int` `data) ` `{ ` `    ``// This function is only ` `    ``// for empty list ` `    ``if` `(head != ``null``) ` `    ``return` `head; ` ` `  `    ``// Creating a node dynamically. ` `    ``Node temp = ``new` `Node(); ` ` `  `    ``// Assigning the data. ` `    ``temp.data = data; ` `    ``head = temp; ` ` `  `    ``// Creating the link. ` `    ``head.next = head; ` ` `  `    ``return` `head; ` `} ` ` `  `static` `Node addBegin(Node head, ` `                     ``int` `data) ` `{ ` `    ``if` `(head == ``null``) ` `        ``return` `addToEmpty(head, data); ` ` `  `    ``Node temp = ``new` `Node(); ` ` `  `    ``temp.data = data; ` `    ``temp.next = head.next; ` `    ``head.next = temp; ` ` `  `    ``return` `head; ` `} ` ` `  `// function for traversing the list  ` `static` `void` `traverse( Node head) ` `{ ` `    ``Node p; ` ` `  `    ``// If list is empty, return. ` `    ``if` `(head == ``null``) ` `    ``{ ` `        ``System.out.print(``"List is empty."``); ` `        ``return``; ` `    ``} ` ` `  `    ``// Pointing to first  ` `    ``// Node of the list. ` `    ``p = head; ` ` `  `    ``// Traversing the list. ` `    ``do` `    ``{ ` `        ``System.out.print(p . data + ``" "``); ` `        ``p = p . next; ` ` `  `    ``} ``while``(p != head); ` `} ` ` `  `// Function to exchange  ` `// first and last node ` `static` `Node exchangeNodes( Node head) ` `{ ` `    ``// Find pointer to previous ` `    ``// of last node ` `    ``Node p = head; ` `    ``while` `(p.next.next != head) ` `    ``p = p.next; ` `     `  `    ``// Exchange first and last  ` `    ``// nodes using head and p ` `    ``p.next.next = head.next; ` `    ``head.next = p.next; ` `    ``p.next = head; ` `    ``head = head.next; ` ` `  `    ``return` `head; ` `} ` ` `  `// Driver Code ` `public` `static` `void` `main(String args[]) ` `{ ` `    ``int` `i; ` `    ``Node head = ``null``; ` `    ``head = addToEmpty(head, ``6``); ` `     `  `    ``for` `(i = ``5``; i > ``0``; i--) ` `    ``head = addBegin(head, i); ` `    ``System.out.print(``"List Before: "``); ` `    ``traverse(head); ` `    ``System.out.println(); ` `     `  `    ``System.out.print(``"List After: "``); ` `    ``head = exchangeNodes(head); ` `    ``traverse(head); ` `} ` `} ` ` `  `// This code is contributed  ` `// by Arnab Kundu `

## C#

 `// C# program to exchange  ` `// first and last node in  ` `// circular linked list  ` `using` `System; ` ` `  `public` `class` `GFG  ` `{  ` ` `  `    ``class` `Node  ` `    ``{  ` `        ``public` `int` `data;  ` `        ``public` `Node next;  ` `    ``};  ` ` `  `    ``static` `Node addToEmpty(Node head,  ` `                        ``int` `data)  ` `    ``{  ` `        ``// This function is only  ` `        ``// for empty list  ` `        ``if` `(head != ``null``)  ` `        ``return` `head;  ` ` `  `        ``// Creating a node dynamically.  ` `        ``Node temp = ``new` `Node();  ` ` `  `        ``// Assigning the data.  ` `        ``temp.data = data;  ` `        ``head = temp;  ` ` `  `        ``// Creating the link.  ` `        ``head.next = head;  ` ` `  `        ``return` `head;  ` `    ``}  ` ` `  `    ``static` `Node addBegin(Node head,  ` `                        ``int` `data)  ` `    ``{  ` `        ``if` `(head == ``null``)  ` `            ``return` `addToEmpty(head, data);  ` ` `  `        ``Node temp = ``new` `Node();  ` ` `  `        ``temp.data = data;  ` `        ``temp.next = head.next;  ` `        ``head.next = temp;  ` ` `  `        ``return` `head;  ` `    ``}  ` ` `  `    ``// function for traversing the list  ` `    ``static` `void` `traverse( Node head)  ` `    ``{  ` `        ``Node p;  ` ` `  `        ``// If list is empty, return.  ` `        ``if` `(head == ``null``)  ` `        ``{  ` `            ``Console.Write(``"List is empty."``);  ` `            ``return``;  ` `        ``}  ` ` `  `        ``// Pointing to first  ` `        ``// Node of the list.  ` `        ``p = head;  ` ` `  `        ``// Traversing the list.  ` `        ``do` `        ``{  ` `            ``Console.Write(p . data + ``" "``);  ` `            ``p = p . next;  ` ` `  `        ``} ``while``(p != head);  ` `    ``}  ` ` `  `    ``// Function to exchange  ` `    ``// first and last node  ` `    ``static` `Node exchangeNodes( Node head)  ` `    ``{  ` `        ``// Find pointer to previous  ` `        ``// of last node  ` `        ``Node p = head;  ` `        ``while` `(p.next.next != head)  ` `        ``p = p.next;  ` ` `  `        ``// Exchange first and last  ` `        ``// nodes using head and p  ` `        ``p.next.next = head.next;  ` `        ``head.next = p.next;  ` `        ``p.next = head;  ` `        ``head = head.next;  ` ` `  `        ``return` `head;  ` `    ``}  ` ` `  `    ``// Driver Code  ` `    ``public` `static` `void` `Main()  ` `    ``{  ` `        ``int` `i;  ` `        ``Node head = ``null``;  ` `        ``head = addToEmpty(head, 6);  ` ` `  `        ``for` `(i = 5; i > 0; i--)  ` `        ``head = addBegin(head, i);  ` `        ``Console.Write(``"List Before: "``);  ` `        ``traverse(head);  ` `        ``Console.WriteLine();  ` ` `  `        ``Console.Write(``"List After: "``);  ` `        ``head = exchangeNodes(head);  ` `        ``traverse(head);  ` `    ``}  ` `}  ` ` `  `/* This code is contributed PrinciRaj1992 */`

Output:

```List Before: 6 1 2 3 4 5
List After: 5 1 2 3 4 6
```