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
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<bits/stdc++.h> 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
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments