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 frontvoid 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. |
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)
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!
