Move last element to front of a given Linked List | Set 2

0 0 4 minutes read

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.

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 zambiatek!