Given the head of a Singly Linked List and a value m, the task is to move the last m elements to the front.
Examples:
Input: 4->5->6->1->2->3 ; m = 3
Output: 1->2->3->4->5->6
Input: 0->1->2->3->4->5 ; m = 4
Output: 2->3->4->5->0->1
Algorithm:
- Use two pointers: one to store the address of the last node and other for the address of the first node.
- Traverse the list till the first node of last m nodes.
- Maintain two pointers p, q i.e., p as the first node of last m nodes & q as just before node of p.
- Make the last node next as the original list head.
- Make the next of node q as NULL.
- Set the p as the head.
Below is the implementation of the above approach.
C++
// C++ Program to move last m elements// to front in a given linked list#include <iostream>using namespace std;// A linked list nodestruct Node { int data; struct Node* next;} * first, *last;int length = 0;// Function to print nodes// in a given linked listvoid printList(struct Node* node){ while (node != NULL) { cout << node->data <<" "; node = node->next; }}// Pointer head and p are being// used here because, the head// of the linked list is changed in this function.void moveToFront(struct Node* head, struct Node* p, int m){ // If the linked list is empty, // or it contains only one node, // then nothing needs to be done, simply return if (head == NULL) return; p = head; head = head->next; m++; // if m value reaches length, // the recursion will end if (length == m) { // breaking the link p->next = NULL; // connecting last to first & // will make another node as head last->next = first; // Making the first node of // last m nodes as root first = head; } else moveToFront(head, p, m);}// UTILITY FUNCTIONS// Function to add a node at// the beginning of Linked Listvoid push(struct Node** head_ref, int new_data){ // allocate node struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); // put in the data new_node->data = new_data; // link the old list of the new node new_node->next = (*head_ref); // move the head to point to the new node (*head_ref) = new_node; // making first & last nodes if (length == 0) last = *head_ref; else first = *head_ref; // increase the length length++;}// Driver codeint main(){ struct Node* start = NULL; // The constructed linked list is: // 1->2->3->4->5 push(&start, 5); push(&start, 4); push(&start, 3); push(&start, 2); push(&start, 1); push(&start, 0); cout << "Initial Linked list\n"; printList(start); int m = 4; // no.of nodes to change struct Node* temp; moveToFront(start, temp, m); cout << "\n Final Linked list\n"; start = first; printList(start); return 0;}// This code is contributed by SHUBHAMSINGH10 |
C
// C Program to move last m elements// to front in a given linked list#include <stdio.h>#include <stdlib.h>// A linked list nodestruct Node { int data; struct Node* next;} * first, *last;int length = 0;// Function to print nodes// in a given linked listvoid printList(struct Node* node){ while (node != NULL) { printf("%d ", node->data); node = node->next; }}// Pointer head and p are being// used here because, the head// of the linked list is changed in this function.void moveToFront(struct Node* head, struct Node* p, int m){ // If the linked list is empty, // or it contains only one node, // then nothing needs to be done, simply return if (head == NULL) return; p = head; head = head->next; m++; // if m value reaches length, // the recursion will end if (length == m) { // breaking the link p->next = NULL; // connecting last to first & // will make another node as head last->next = first; // Making the first node of // last m nodes as root first = head; } else moveToFront(head, p, m);}// UTILITY FUNCTIONS// Function to add a node at// the beginning of Linked Listvoid push(struct Node** head_ref, int new_data){ // allocate node struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); // put in the data new_node->data = new_data; // link the old list of the new node new_node->next = (*head_ref); // move the head to point to the new node (*head_ref) = new_node; // making first & last nodes if (length == 0) last = *head_ref; else first = *head_ref; // increase the length length++;}// Driver codeint main(){ struct Node* start = NULL; // The constructed linked list is: // 1->2->3->4->5 push(&start, 5); push(&start, 4); push(&start, 3); push(&start, 2); push(&start, 1); push(&start, 0); printf("\n Initial Linked list\n"); printList(start); int m = 4; // no.of nodes to change struct Node* temp; moveToFront(start, temp, m); printf("\n Final Linked list\n"); start = first; printList(start); return 0;} |
Java
// Java Program to move last m elements// to front in a given linked listclass GFG { // A linked list node static class Node { int data; Node next; } static Node first, last; static int length = 0; // Function to print nodes // in a given linked list static void printList(Node node) { while (node != null) { System.out.printf("%d ", node.data); node = node.next; } } // Pointer head and p are being // used here because, the head // of the linked list is changed in this function. static void moveToFront(Node head, Node p, int m) { // If the linked list is empty, // or it contains only one node, // then nothing needs to be done, simply return if (head == null) return; p = head; head = head.next; m++; // if m value reaches length, // the recursion will end if (length == m) { // breaking the link p.next = null; // connecting last to first & // will make another node as head last.next = first; // Making the first node of // last m nodes as root first = head; } else moveToFront(head, p, m); } // UTILITY FUNCTIONS // Function to add a node at // the beginning of Linked List static Node push(Node head_ref, int new_data) { // allocate node Node new_node = new Node(); // put in the data new_node.data = new_data; // link the old list of the new node new_node.next = head_ref; // move the head to point to the new node head_ref = new_node; // making first & last nodes if (length == 0) last = head_ref; else first = head_ref; // increase the length length++; return head_ref; } // Driver code public static void main(String[] args) { Node start = null; // The constructed linked list is: // 1.2.3.4.5 start = push(start, 5); start = push(start, 4); start = push(start, 3); start = push(start, 2); start = push(start, 1); start = push(start, 0); System.out.printf("\n Initial Linked list\n"); printList(start); int m = 4; // no.of nodes to change Node temp = new Node(); moveToFront(start, temp, m); System.out.printf("\n Final Linked list\n"); start = first; printList(start); }}// This code is contributed by 29AjayKumar |
Python3
# Python Program to move last m elements# to front in a given linked list# A linked list nodeclass Node : def __init__(self): self.data = 0 self.next = None first = Nonelast = Nonelength = 0# Function to print nodes# in a given linked listdef printList( node): while (node != None) : print( node.data, end=" ") node = node.next # Pointer head and p are being# used here because, the head# of the linked list is changed in this function.def moveToFront( head, p, m): global first global last global length # If the linked list is empty, # or it contains only one node, # then nothing needs to be done, simply return if (head == None): return head p = head head = head.next m= m + 1 # if m value reaches length, # the recursion will end if (length == m) : # breaking the link p.next = None # connecting last to first & # will make another node as head last.next = first # Making the first node of # last m nodes as root first = head else: moveToFront(head, p, m) # UTILITY FUNCTIONS# Function to add a node at# the beginning of Linked Listdef push( head_ref, new_data): global first global last global length # allocate node new_node = Node() # put in the data new_node.data = new_data # link the old list of the new node new_node.next = (head_ref) # move the head to point to the new node (head_ref) = new_node # making first & last nodes if (length == 0): last = head_ref else: first = head_ref # increase the length length= length + 1 return head_ref# Driver codestart = None# The constructed linked list is:# 1.2.3.4.5start = push(start, 5)start = push(start, 4)start = push(start, 3)start = push(start, 2)start = push(start, 1)start = push(start, 0)print("\n Initial Linked list")printList(start)m = 4 # no.of nodes to changetemp = NonemoveToFront(start, temp, m)print("\n Final Linked list")start = firstprintList(start)# This code is contributed by Arnab Kundu |
C#
// C# Program to move last m elements// to front in a given linked listusing System;class GFG { // A linked list node class Node { public int data; public Node next; } static Node first, last; static int length = 0; // Function to print nodes // in a given linked list static void printList(Node node) { while (node != null) { Console.Write("{0} ", node.data); node = node.next; } } // Pointer head and p are being used here // because, the head of the linked list // is changed in this function. static void moveToFront(Node head, Node p, int m) { // If the linked list is empty, // or it contains only one node, // then nothing needs to be done, // simply return if (head == null) return; p = head; head = head.next; m++; // if m value reaches length, // the recursion will end if (length == m) { // breaking the link p.next = null; // connecting last to first & // will make another node as head last.next = first; // Making the first node of // last m nodes as root first = head; } else moveToFront(head, p, m); } // UTILITY FUNCTIONS // Function to add a node at // the beginning of Linked List static Node push(Node head_ref, int new_data) { // allocate node Node new_node = new Node(); // put in the data new_node.data = new_data; // link the old list of the new node new_node.next = head_ref; // move the head to point to the new node head_ref = new_node; // making first & last nodes if (length == 0) last = head_ref; else first = head_ref; // increase the length length++; return head_ref; } // Driver code public static void Main(String[] args) { Node start = null; // The constructed linked list is: // 1.2.3.4.5 start = push(start, 5); start = push(start, 4); start = push(start, 3); start = push(start, 2); start = push(start, 1); start = push(start, 0); Console.Write("Initial Linked list\n"); printList(start); int m = 4; // no.of nodes to change Node temp = new Node(); moveToFront(start, temp, m); Console.Write("\nFinal Linked list\n"); start = first; printList(start); }}// This code is contributed by PrinciRaj1992 |
Javascript
<script> // JavaScript Program to move last m elements // to front in a given linked list // A linked list node class Node { constructor() { this.data = 0; this.next = null; } } var first, last; var length = 0; // Function to print nodes // in a given linked list function printList(node) { while (node != null) { document.write(node.data + " "); node = node.next; } } // Pointer head and p are being used here // because, the head of the linked list // is changed in this function. function moveToFront(head, p, m) { // If the linked list is empty, // or it contains only one node, // then nothing needs to be done, // simply return if (head == null) return; p = head; head = head.next; m++; // if m value reaches length, // the recursion will end if (length == m) { // breaking the link p.next = null; // connecting last to first & // will make another node as head last.next = first; // Making the first node of // last m nodes as root first = head; } else moveToFront(head, p, m); } // UTILITY FUNCTIONS // Function to add a node at // the beginning of Linked List function push(head_ref, new_data) { // allocate node var new_node = new Node(); // put in the data new_node.data = new_data; // link the old list of the new node new_node.next = head_ref; // move the head to point to the new node head_ref = new_node; // making first & last nodes if (length == 0) last = head_ref; else first = head_ref; // increase the length length++; return head_ref; } // Driver code var start = null; // The constructed linked list is: // 1.2.3.4.5 start = push(start, 5); start = push(start, 4); start = push(start, 3); start = push(start, 2); start = push(start, 1); start = push(start, 0); document.write("Initial Linked list <br>"); printList(start); var m = 4; // no.of nodes to change var temp = new Node(); moveToFront(start, temp, m); document.write("<br> Final Linked list <br>"); start = first; printList(start); // This code is contributed by rdtank. </script> |
Output:
Initial Linked list 0 1 2 3 4 5 Final Linked list 2 3 4 5 0 1
Time Complexity: O(n), where n represents the length of the list.
Auxiliary Space: O(1), no extra space is required, so it is a constant.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
