Last Updated on November 14, 2022 by Prepbytes
This blog consists of step by step solving to move last element to front of a linked list. Linked list is the most important part of data structures. Having knowledge about data structures will increase the logic building and problem solving skills. Let’s deep dive into our topic to move last element to first in linked list.
How To Move Last Element To Front Of A Linked List
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):
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 To Move Last Element To Front Of A Linked List
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 To Move Last Element To Front Of A Linked List
Code Implementation To Move Last Element To Front Of A Linked List
#include<stdio.h>
#include<stdlib.h>
/* A linked list node */
struct Node
{
int data;
struct Node *next;
};
/* We are using a double pointer head_ref here because we change
head of the linked list inside this function.*/
void moveToFront(struct Node **head_ref)
{
/* If linked list is empty, or it contains only one node,
then nothing needs to be done, simply return */
if (*head_ref == NULL || (*head_ref)->next == NULL)
return;
/* Initialize second last and last pointers */
struct Node *secLast = NULL;
struct Node *last = *head_ref;
/*After this loop secLast contains address of second last
node and last contains address of last node in Linked List */
while (last->next != NULL)
{
secLast = last;
last = last->next;
}
/* Set the next of second last as NULL */
secLast->next = NULL;
/* Set next of last as head node */
last->next = *head_ref;
/* Change the head pointer to point to last node now */
*head_ref = last;
}
/* UTILITY FUNCTIONS */
/* Function to add a node at the beginning of Linked List */
void 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 off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given linked list */
void printList(struct Node *node)
{
while(node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
}
/* Driver program to test above function */
int 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);
printf("\n Linked list before moving last to front\n");
printList(start);
moveToFront(&start);
printf("\n Linked list after removing last to front\n");
printList(start);
return 0;
}
#include <bits stdc++.h="">
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;
}
class MoveLast
{
Node head;
class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}
void moveToFront()
{
if(head == null || head.next == null)
return;
/* Initialize second last and last pointers */
Node secLast = null;
Node last = head;
while (last.next != null)
{
secLast = last;
last = last.next;
}
secLast.next = null;
last.next = head;
head = last;
}
void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
void printList()
{
Node temp = head;
while(temp != null)
{
System.out.print(temp.data+" ");
temp = temp.next;
}
System.out.println();
}
public static void main(String args[])
{
MoveLast llist = new MoveLast();
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);
System.out.println("Linked List before moving last to front ");
llist.printList();
llist.moveToFront();
System.out.println("Linked List after moving last to front ");
llist.printList();
}
}
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def printList(self):
tmp = self.head
while tmp is not None:
print(tmp.data, end=" ")
tmp = tmp.next
print()
def moveToFront(self):
tmp = self.head
sec_last = None
if not tmp or not tmp.next:
return
while tmp and tmp.next :
sec_last = tmp
tmp = tmp.next
sec_last.next = None
tmp.next = self.head
self.head = tmp
if __name__ == '__main__':
llist = LinkedList()
llist.push(1)
llist.push(3)
llist.push(5)
llist.push(7)
llist.moveToFront()
llist.printList()
Output
1 7 5 3
Time Complexity To Move Last Element To Front Of A Linked List: O(n), where n is the number of nodes in the given LinkedList.
Space Complexity To Move Last Element To Front Of A Linked List: O(1), constant space complexity, as no extra space is used.
This blog taught us an efficient approach of solving the problem “Move last element to first in linked list” with best illustration of approach, algorithm, and dry run to move last element to first in linked list. Linked list is a topic which should be practiced for placing in tech companies like Amazon, Adobe, Google, Flipkart etc. If you want to practice more questions on linked lists, feel free to solve them atLinked List.
FAQ
- What is the linked list? A linked list is a sequence of data structures, which are connected together via links. Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list is the second most-used data structure after array.
- What is the node in the linked list? A node is a collection of two sub-elements or parts. A data part that stores the element and a next part that stores the link to the next node.
- Which companies asked questions about linked lists in their interviews? Companies like Josh Technologies, Samsung, Uber, Indiamart and Amazon asked questions related to linked lists in their interviews.