Given a Linked List move the last element to the front

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we are given a linked list, and we have to move the last node of the linked list to the very first and make it head or root.

Input:

Output (After moving the last element to the front of the linked list):

Problem Statement Understanding

Let’s try to understand the problem by taking an example.
Initial Linked list = 7 → 5 → 3 → 1

  • We will start with traversing the linked list from the head until we have reached the last node of the linked list.
  • Once we have reached the last node of the linked list, we will make the previous node of the last node point to NULL and the next of the last node will point to the head node.
  • Finally, we will make the node which we inserted at the front of the linked list the new head of the linked list.

After moving the last node to the front of the linked list, our linked list will look like:
Updated Linked list = 1 → 7 → 5 → 3.

Well, this is a very basic problem, and furthermore we will continue with the approach to solve the problem.

Approach and Algorithm

The most naive idea is to traverse the list till the last node or end of the LinkedList. Use two node pointers last and secLast - last used to store the address of the last node and the secLast is used to store the address of the second last node. After the end of the loop, do the following operations.

  • We have to make the second last as last (secLast->next = NULL).
  • Next step is to change next of last as head (_last->next = *headref).
  • The final step is to make last as the head (_*headref = last).

Dry Run

Code Implementation


#include 
using namespace std;
class Node
{
    public:
    int data;
    Node *next;
};
void moveToFront(Node **head_ref)
{
    if (*head_ref == NULL || *head_ref->next == NULL)
        return;
    Node *secLast = NULL;
    Node *last = *head_ref;
    while (last->next != NULL)
    {
        secLast = last;
        last = last->next;
    }
    secLast->next = NULL;
    last->next = *head_ref;
    *head_ref = last;
}
void push(Node** head_ref, int new_data)
{
    Node* new_node = new Node();
    new_node->data = new_data;
    new_node->next = *head_ref;
    *head_ref = new_node;
}
void printList(Node *node)
{
    while(node != NULL)
    {
        cout << node->data << " ";
        node = node->next;
    }
}
int main()
{
    Node *start = NULL;
    push(&start, 1);
    push(&start, 3);
    push(&start, 5);
    push(&start, 7);
    moveToFront(&start);
    printList(start);
    return 0;
}

Output

1 7 5 3

Time Complexity: O(n), where n is the number of nodes in the given LinkedList.

Space complexity: O(1), constant space complexity, as no extra space is used.

This blog tried to discuss how you can move the last element of the linked list to the front of the list by changing the links and not just by copying the data. If you want to practice more questions on linked lists, feel free to solve them at Linked List.

Previous post The intersection of two Sorted Linked Lists
Next post Identical Linked Lists

Leave a Reply

Your email address will not be published. Required fields are marked *