Move last element to front of a given Linked List | Set 2
Given a singly linked list and an integer K. The task is to append last K elements of the linked list to front. Examples:
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6, k = 3
Output : 4 -> 5 -> 6 -> 1 -> 2 -> 3
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6, k = 7
Output : 6 -> 1 -> 2 -> 3 -> 4 -> 5
Prerequisites: Move last element to front of a given Linked List Approach:
- Loop over (k % n) times, Where n is the number of elements of the linked list.
- Each time, delete one node from the end of the linked list.
- Simultaneously insert that deleted node at the beginning of the linked list.
Below is the implementation of the above approach :
C++
// CPP Program to move k last elements // to front in a given linked list #include<iostream> using namespace std; // A linked list node class Node { public : int data; Node* next; Node( int d) { data = d; next = NULL; } }; // Function to add a new node at the // end/tail of Linked List void insertAtTail(Node*& head, Node*& tail, int d ) { Node* newnode = new Node(d); if (tail == NULL) { tail = head = newnode; return ; } tail->next = newnode; tail = newnode; } // Function to add a node at the // beginning of Linked List void insertAtHead(Node*& head, Node*& tail, Node*& deletedNode) { if (head == NULL) { head = tail = deletedNode; return ; } deletedNode->next = head; head = deletedNode; return ; } // Function to add a node at the beginning of Linked List Node* deleteAtTail(Node*& head, Node*& tail) { Node* deleted = tail; Node* temp = head; while (temp->next->next != NULL) { temp = temp->next; } temp->next = NULL; tail = temp; return deleted; } // k can be more than n, so this function takes the modulus // of k with n and delete nodes from end k // times and simultaneously insert it in front void appendAtFront(Node*& head, Node*& tail, int n, int k) { k = k % n; while (k != 0) { Node* deleted = deleteAtTail(head, tail); insertAtHead(head, tail, deleted); k--; } } // Function to print nodes in a given linked list void printLinkedList(Node* head) { while (head != NULL) { cout << head->data << " " ; head = head->next; } cout << endl; } // Driver Code int main() { // Pointer to the start of the linked list Node* head = NULL; // Pointer to the end of the linked list Node* tail = NULL; // Number of elements in the linked list int n = 6; // Building linked list insertAtTail(head, tail, 1); insertAtTail(head, tail, 2); insertAtTail(head, tail, 3); insertAtTail(head, tail, 4); insertAtTail(head, tail, 5); insertAtTail(head, tail, 6); // Printing linked list before // appending the linked list cout << "Linked List before appending: " ; printLinkedList(head); // Number of elements to be appended int k = 7; // Function call appendAtFront(head, tail, n, k); // Printing linked list after appending the list cout << "Linked List after appending " <<k<< " elements: " ; printLinkedList(head); } |
Java
// JAVA Program to move k last elements // to front in a given linked list import java.io.*; class Node { int data; Node next; Node( int data) { this .data = data; this .next = null ; } } class LinkedList { Node head; Node tail; // Function to add a new node at the end/tail of Linked // List public void insertAtTail( int data) { Node newnode = new Node(data); if (tail == null ) { tail = head = newnode; return ; } tail.next = newnode; tail = newnode; } // Function to add a node at the beginning of Linked // List public void insertAtHead(Node deletedNode) { if (head == null ) { head = tail = deletedNode; return ; } deletedNode.next = head; head = deletedNode; } // Function to delete a node at the end of Linked List public Node deleteAtTail() { Node deleted = tail; Node temp = head; while (temp.next.next != null ) { temp = temp.next; } temp.next = null ; tail = temp; return deleted; } // k can be more than n, so this function takes the // modulus of k with n and delete nodes from end k times // and simultaneously insert it in front public void appendAtFront( int n, int k) { k = k % n; while (k != 0 ) { Node deleted = deleteAtTail(); insertAtHead(deleted); k--; } } // Function to print nodes in a given linked list public void printLinkedList() { Node temp = head; while (temp != null ) { System.out.print(temp.data + " " ); temp = temp.next; } System.out.println(); } } class GFG { public static void main(String[] args) { LinkedList ll = new LinkedList(); ll.insertAtTail( 1 ); ll.insertAtTail( 2 ); ll.insertAtTail( 3 ); ll.insertAtTail( 4 ); ll.insertAtTail( 5 ); ll.insertAtTail( 6 ); System.out.print( "Linked List before appending: " ); ll.printLinkedList(); int k = 7 ; ll.appendAtFront( 6 , k); System.out.print( "Linked List after appending " + k + " elements: " ); ll.printLinkedList(); } } // This code is contributed by lokesh. |
Python3
class Node: def __init__( self , data): self .data = data self . next = None class LinkedList: def __init__( self ): self .head = None self .tail = None # Function to add a new node at the end/tail of Linked List def insert_at_tail( self , data): new_node = Node(data) if self .tail is None : self .tail = self .head = new_node return self .tail. next = new_node self .tail = new_node # Function to add a node at the beginning of Linked List def insert_at_head( self , deleted_node): if self .head is None : self .head = self .tail = deleted_node return deleted_node. next = self .head self .head = deleted_node # Function to delete a node at the end of Linked List def delete_at_tail( self ): deleted = self .tail temp = self .head while temp. next . next is not None : temp = temp. next temp. next = None self .tail = temp return deleted # k can be more than n, so this function takes the modulus # of k with n and deletes nodes from the end k times while # simultaneously inserting them at the front def append_at_front( self , n, k): k = k % n while k ! = 0 : deleted = self .delete_at_tail() self .insert_at_head(deleted) k - = 1 # Function to print nodes in a given linked list def print_linked_list( self ): temp = self .head while temp is not None : print (temp.data, end = " " ) temp = temp. next print () # Driver Code if __name__ = = "__main__" : ll = LinkedList() ll.insert_at_tail( 1 ) ll.insert_at_tail( 2 ) ll.insert_at_tail( 3 ) ll.insert_at_tail( 4 ) ll.insert_at_tail( 5 ) ll.insert_at_tail( 6 ) print ( "Linked List before appending: " , end = "") ll.print_linked_list() k = 7 ll.append_at_front( 6 , k) print ( "Linked List after appending" , k, "elements: " , end = "") ll.print_linked_list() |
C#
using System; class Node { public int data; public Node next; public Node( int data) { this .data = data; this .next = null ; } } class LinkedList { public Node head; public Node tail; // Function to add a new node at the end/tail of Linked // List public void InsertAtTail( int data) { Node newNode = new Node(data); if (tail == null ) { tail = head = newNode; return ; } tail.next = newNode; tail = newNode; } // Function to add a node at the beginning of Linked // List public void InsertAtHead(Node deletedNode) { if (head == null ) { head = tail = deletedNode; return ; } deletedNode.next = head; head = deletedNode; } // Function to delete a node at the end of Linked List public Node DeleteAtTail() { Node deleted = tail; Node temp = head; while (temp.next.next != null ) { temp = temp.next; } temp.next = null ; tail = temp; return deleted; } // k can be more than n, so this function takes the // modulus of k with n and deletes nodes from the end k // times while simultaneously inserting them at the // front public void AppendAtFront( int n, int k) { k = k % n; while (k != 0) { Node deleted = DeleteAtTail(); InsertAtHead(deleted); k--; } } // Function to print nodes in a given linked list public void PrintLinkedList() { Node temp = head; while (temp != null ) { Console.Write(temp.data + " " ); temp = temp.next; } Console.WriteLine(); } } class Program { public static void Main() { LinkedList ll = new LinkedList(); ll.InsertAtTail(1); ll.InsertAtTail(2); ll.InsertAtTail(3); ll.InsertAtTail(4); ll.InsertAtTail(5); ll.InsertAtTail(6); Console.Write( "Linked List before appending: " ); ll.PrintLinkedList(); int k = 7; ll.AppendAtFront(6, k); Console.Write( "Linked List after appending " + k + " elements: " ); ll.PrintLinkedList(); } } |
Javascript
class Node { constructor(data) { this .data = data; this .next = null ; } } class LinkedList { constructor() { this .head = null ; this .tail = null ; } // Function to add a new node at the end/tail of Linked List insertAtTail(data) { const newNode = new Node(data); if ( this .tail === null ) { this .tail = this .head = newNode; return ; } this .tail.next = newNode; this .tail = newNode; } // Function to add a node at the beginning of Linked List insertAtHead(deletedNode) { if ( this .head === null ) { this .head = this .tail = deletedNode; return ; } deletedNode.next = this .head; this .head = deletedNode; } // Function to delete a node at the end of Linked List deleteAtTail() { if ( this .head === null ) { return null ; // Empty list, nothing to delete } const deleted = this .tail; let temp = this .head; // If there is only one element in the list if (temp === this .tail) { this .head = this .tail = null ; return deleted; } while (temp.next.next !== null ) { temp = temp.next; } temp.next = null ; this .tail = temp; return deleted; } // k can be more than n, so this function takes the // modulus of k with n and delete nodes from end k times // and simultaneously insert it in front appendAtFront(n, k) { k = k % n; while (k !== 0) { const deleted = this .deleteAtTail(); this .insertAtHead(deleted); k--; } } // Function to print nodes in a given linked list printLinkedList() { let temp = this .head; while (temp !== null ) { process.stdout.write(temp.data + " " ); temp = temp.next; } console.log(); } } // Driver Code const ll = new LinkedList(); ll.insertAtTail(1); ll.insertAtTail(2); ll.insertAtTail(3); ll.insertAtTail(4); ll.insertAtTail(5); ll.insertAtTail(6); process.stdout.write( "Linked List before appending: " ); ll.printLinkedList(); const k = 7; ll.appendAtFront(6, k); process.stdout.write( "Linked List after appending " + k + " elements: " ); ll.printLinkedList(); |
Output
Linked List before appending: 1 2 3 4 5 6 Linked List after appending 7 elements: 6 1 2 3 4 5
Time Complexity: O(N)
Auxiliary Space: O(1)
Contact Us