Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Linked list articles

Remove the last node of a linked list

Aman Sharma

In this blog, we will learn how to delete last node in linked list. Basically, we see two conditions one is that there is only one in the linked list and another one is that the linked list can have more than one node and the last node of the linked list have to delete. let’s try to understand how to delete last node in linked list

How to Delete Last Node in Linked List

In this question, we are given a singly linked list. We have to remove the last node of the given list.

Suppose, the given linked list is 1 -> 5 -> 9 -> 11 -> 20. Now, we are asked to delete the last node of the given list.

Here, the last node is 20. So, after deleting the last node, the final linked list is 1 -> 5 -> 9 -> 11.

Input:

Output:

Explanation: As the last node is 20, it is getting removed from the given list.

As we know, insertion and deletion in a singly linked list are very efficient, but list traversal takes O(n) time. We are going to use the list traversal, but with a few tweaks. Let us have a glance at the approach.

Approach to delete last node in linked list

The approach is going to be pretty simple to delete last node in linked list. To remove the last node, what we can do is, reach the second last node, and make it point to NULL. By doing this, we are deleting the last node and making the second last node our new last node.

Algorithm to delete last node in linked list

  • Base Case 1 – If the head is NULL, return NULL
  • Base Case 2 – if head -> next is NULL, delete the head and return NULL.
  • This means that there was only a single node in the linked list.
  • Create a new node, say SecondLast and make it point to the head of the list.
  • Now, traverse through the list by incrementing SecondLast, till the second last node of the linked list is reached.
  • When we reach the second last node of the linked list, simply delete the next of the second last node i.e delete the last node.
  • delete(SecondLast -> next).
  • Make the second last node point to NULL. This will make our second last node new tail of the list.
  • Return head.

Dry Run to delete last node in linked list

Code Implementation to delete last node in linked list

#include <stdio.h>
#include<stdlib.h>

struct Node {
    int data;
    struct Node* next;
};
 
/* Function to remove the last node 
   of the linked list */
struct Node* removeLastNode(struct Node* head)
{
    if (head == NULL)
        return NULL;
 
    if (head->next == NULL) {
        free(head);
        return NULL;
    }
 
    // Find the second last node
    struct Node* second_last = head;
    while (second_last->next->next != NULL)
        second_last = second_last->next;
 
    // Delete last node
    free(second_last->next);
 
    // Change next of second last
    second_last->next = NULL;
 
    return head;
}
 
// Function to push node at head
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node =
         (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
 
// Driver code
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
 
    /* Use push() function to construct  
       the below list 8 -> 23 -> 11 -> 29 -> 12 */
    push(&head, 12);
    push(&head, 29);
    push(&head, 11);
    push(&head, 23);
    push(&head, 8);
 
    head = removeLastNode(head);
    for (struct Node* temp = head; temp != NULL; temp = temp->next)
        printf("%d ",temp->data);
 
    return 0;
}


#include <iostream>
using namespace std;

struct Node {
    int data;
    struct Node* next;
};

Node* removeLastNode(struct Node* head)
{
    if (head == NULL)
        return NULL;
 
    if (head->next == NULL) {
        delete head;
        return NULL;
    }

    Node* second_last = head;
    while (second_last->next->next != NULL)
        second_last = second_last->next;

    delete (second_last->next);

    second_last->next = NULL;
 
    return head;
}

void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

int main()
{

    Node* head = NULL;

    push(&head, 20);
    push(&head, 11);
    push(&head, 9);
    push(&head, 5);
    push(&head, 1);
 
    head = removeLastNode(head);
    for (Node* temp = head; temp != NULL; temp = temp->next)
        cout << temp->data << " ";
 
    return 0;
}


public class PrepBytes {

    static class Node {
        int data;
        Node next;
    };

    static Node removeLastNode(Node head)
    {
        if (head == null)
            return null;
 
        if (head.next == null) {
            return null;
        }

        Node second_last = head;
        while (second_last.next.next != null)
            second_last = second_last.next;

        second_last.next = null;
 
        return head;
    }

    static Node 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;
        return head_ref;
    }

    public static void main(String args[])
    {
        Node head = null;
        head = push(head, 20);
        head = push(head, 11);
        head = push(head, 9);
        head = push(head, 5);
        head = push(head, 1);
        head = removeLastNode(head);
        for (Node temp = head; temp != null; temp = temp.next)
            System.out.print(temp.data + " ");
    }
}

class Node:
	def __init__(self, data):
		self.data = data
		self.next = None

def push(head, data):
	if not head:
		return Node(data)
	temp = Node(data)
	temp.next = head
	head = temp
	return head

def removeLastNode(head):
	if head == None:
		return None
	if head.next == None:
		head = None
		return None
	second_last = head
	while(second_last.next.next):
		second_last = second_last.next
	second_last.next = None
	return head

if __name__=='__main__':

	head = None
	head = push(head, 20)
	head = push(head, 11)
	head = push(head, 9)
	head = push(head, 5)
	head = push(head, 1)

	head = removeLastNode(head)
	while(head):
		print("{} ".format(head.data), end ="")
		head = head.next

Output

1 5 9 11

Space Complexity: O(1), as only temporary variables are bring created.

So, in this article, we have tried to explain the most efficient approach to remove the last node of a linked list. This problem tests our basic concepts of linked lists and an important one for coding interviews because of some following secnarios. If you want to solve more questions on Linked List, you can follow this link Linked List.

FAQs on how to delete last node in linked list.

1. What are the three conditions for deleting nodes in the linked list?
To delete the node from the linked list:

  • Find the previous node of the node to be deleted.
  • Change the next to the previous node.
  • Free up the memory for the node to be deleted.

2. What is the time complexity of deleting the last node?
In the worst case, the pointer has to go all the way to the second last node by traversing (n-1) positions.so O(n) time will be required.

3. Does the head of the linked list have data?
It is a list node that contains no actual data. A reference or pointer to the list is always a pointer to the head node

Leave a Reply

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

Close

Related Post