Problem Statement:
You are given an LL, you need to move the last element to the first.
Example
Input: 1->2->3->4->5 Output: 5->1->2->3->4.
Solution
The solution is very simple.
Traverse till the last node.
Then perform below operations:
1. Make the second last as last
2. Set the last node as head.
3. Make it as new head.
Solution in C++
#include <vector> #include <algorithm> //visit www.ProDeveloperTutorial.com for 450+ solved questions #include <iostream> #include <string> #include <unordered_map> #include <vector> #include <sstream> using namespace std; #include<iostream> #include<vector> using namespace std; struct Node { int data; struct Node* next; }; void insert_at_begenning ( struct Node **head_pointer, int data) { // allocate memory for new node struct Node *temp_node = (struct Node*) malloc(sizeof(struct Node)); // assign the data to new node temp_node->data = data; // initialize the new node to point to NULL temp_node->next = NULL; // if this is the first pointer, then this is the head pointer if (*head_pointer == NULL) { *head_pointer = temp_node; } else { // point the next of the present pointer to the head pointer temp_node->next = *head_pointer; //then move the reference of head pointer to the current pointer *head_pointer = temp_node; } } void display_list(struct Node **head_pointer) { // take a reference to head pointer for navigation struct Node *temp = *head_pointer; while(temp != NULL) { if(temp->next != NULL) printf("%d -> ", temp->data); else printf("%d", temp->data); //navigate to next pointer temp = temp->next; } printf("\n"); } void move_to_front(Node **head_ref) { if (*head_ref == NULL || (*head_ref)->next == NULL) return; Node *sec_last = NULL; Node *last = *head_ref; while (last->next != NULL) { sec_last = last; last = last->next; } sec_last->next = NULL; last->next = *head_ref; *head_ref = last; } int main() { struct Node *list_1 = NULL; struct Node *result = NULL; int k = 2; insert_at_begenning(&list_1,5); insert_at_begenning(&list_1,4); insert_at_begenning(&list_1,3); insert_at_begenning(&list_1,2); insert_at_begenning(&list_1,1); insert_at_begenning(&list_1,3); insert_at_begenning(&list_1,2); insert_at_begenning(&list_1,1); printf("Original List\n"); display_list(&list_1); move_to_front(&list_1); printf("The result list is\n"); display_list(&list_1); return 0; }
Output:
Original List 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 4 -> 5 The result list is 5 -> 1 -> 2 -> 3 -> 1 -> 2 -> 3 -> 4