How do you delete the last element in a linked list?

Remove last node of the linked list

Given a linked list, the task is to remove the last node of the linked list and update the head pointer of the linked list.

Table of Contents Show

Remove last node of the linked list
Deletion in singly linked list at the end
C Exercises: Delete the last node of Singly Linked List
Logic to Delete the Last Node of a Linked List

Examples:

Input: 1 -> 2 -> 3 -> 4 -> 5 -> NULL Output: 1 -> 2 -> 3 -> 4 -> NULL Explanation: The last node of the linked list is 5, so 5 is deleted. Input: 2 -> 4 -> 6 -> 8 -> 33 -> 67 -> NULL Output: 2 -> 4 -> 6 -> 8 -> 33 -> NULL Explanation: The last node of the linked list is 67, so 67 is deleted.

Recommended: Please try your approach on {IDE} first, before moving on to the solution.

Approach: To delete the last node of a linked list, find the second last node and make the next pointer of that node null.

Algorithm:

1. If the first node is null or there is only one node, then they return null.

if headNode == null then return null if headNode.nextNode == null then free head and return null

2. Create an extra space secondLast, and traverse the linked list till the second last node.

while secondLast.nextNode.nextNode != null secondLast = secondLast.nextNode

3. delete the last node, i.e. the next node of the second last node delete(secondLast.nextNode), and set the value of the next second-last node to null.

Implementation:

C++

// CPP program to remove last node of
// linked list.
#include <iostream>

using namespace std;
/* Link list node */

struct Node {

int data;

struct Node* next;
};
/* Function to remove the last node 

of the linked list */

Node* removeLastNode(struct Node* head)
{

if (head == NULL)

return NULL;

if (head->next == NULL) {

delete head;

return NULL;

}

// Find the second last node

Node* second_last = head;

while (second_last->next->next != NULL)

second_last = second_last->next;

// Delete last node

delete (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 = new Node;

new_node->data = new_data;

new_node->next = (*head_ref);

(*head_ref) = new_node;
}
// Driver code

int main()
{

/* Start with the empty list */

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 (Node* temp = head; temp != NULL; temp = temp->next)

cout << temp->data << " ";

return 0;
}

Java

// Java program to remove last node of
// linked list.

class GFG {

// Link list node /

static class Node {

int data;

Node next;

};

// Function to remove the last node

// of the linked list /

static Node removeLastNode(Node head)

{

if (head == null)

return null;

if (head.next == null) {

return null;

}

// Find the second last node

Node second_last = head;

while (second_last.next.next != null)

second_last = second_last.next;

// Change next of second last

second_last.next = null;

return head;

}

// Function to push node at 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;

}

// Driver code

public static void main(String args[])

{

// Start with the empty list /

Node head = null;

// Use push() function to con

// the below list 8 . 23 . 11 . 29 . 12 /

head = push(head, 12);

head = push(head, 29);

head = push(head, 11);

head = push(head, 23);

head = push(head, 8);

head = removeLastNode(head);

for (Node temp = head; temp != null; temp = temp.next)

System.out.print(temp.data + " ");

}
}
// This code is contributed by Arnab Kundu

Python3

# Python3 program to remove the last node of 
# linked list.

import sys

import math
# Link list node

class Node:

def __init__(self, data):

self.data = data

self.next = None
# Function to push node at head 

def push(head, data):

if not head:

return Node(data)

temp = Node(data)

temp.next = head

head = temp

return head
# Function to remove the last node 
# of the linked list

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
# Driver code

if __name__=='__main__':

# Start with the empty list

head = None

# Use push() function to con

# the below list 8 . 23 . 11 . 29 . 12

head = push(head, 12)

head = push(head, 29)

head = push(head, 11)

head = push(head, 23)

head = push(head, 8)

head = removeLastNode(head)

while(head):

print("{} ".format(head.data), end ="")

head = head.next
# This code is contributed by Vikash kumar 37

// C# program to remove last node of
// linked list.

using System;

class GFG {

// Link list node /

public class Node {

public int data;

public Node next;

};

// Function to remove the last node

// of the linked list /

static Node removeLastNode(Node head)

{

if (head == null)

return null;

if (head.next == null) {

return null;

}

// Find the second last node

Node second_last = head;

while (second_last.next.next != null)

second_last = second_last.next;

// Change next of second last

second_last.next = null;

return head;

}

// Function to push node at 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;

}

// Driver code

public static void Main(String[] args)

{

// Start with the empty list /

Node head = null;

// Use push() function to con

// the below list 8 . 23 . 11 . 29 . 12 /

head = push(head, 12);

head = push(head, 29);

head = push(head, 11);

head = push(head, 23);

head = push(head, 8);

head = removeLastNode(head);

for (Node temp = head; temp != null; temp = temp.next)

Console.Write(temp.data + " ");

}
}
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
// javascript program to remove last node of
// linked list. // Link list node /

class Node {

constructor() {

this.data = 0;

this.next = null;

}

}

// Function to remove the last node

// of the linked list /

function removeLastNode(head)

{

if (head == null)

return null;

if (head.next == null) {

return null;

}

// Find the second last node

var second_last = head;

while (second_last.next.next != null)

second_last = second_last.next;

// Change next of second last

second_last.next = null;

return head;

}

// Function to push node at head

function push(head_ref , new_data)

{

var new_node = new Node();

new_node.data = new_data;

new_node.next = (head_ref);

(head_ref) = new_node;

return head_ref;

}

// Driver code

// Start with the empty list /

var head = null;

// Use push() function to con

// the below list 8 . 23 . 11 . 29 . 12 /

head = push(head, 12);

head = push(head, 29);

head = push(head, 11);

head = push(head, 23);

head = push(head, 8);

head = removeLastNode(head);

for (temp = head; temp != null; temp = temp.next)

document.write(temp.data + " ");
// This code contributed by Rajput-Ji
</script>

Output: 8 23 11 29

Complexity Analysis:

Time Complexity: O(n).
The algorithm involves traversal of the linked list till its end, so the time complexity required is O(n).
Space Complexity: O(1).
No extra space is required, so the space complexity is constant.

Article Tags :

Data Structures

Linked List

Technical Scripter

Technical Scripter 2018

Practice Tags :

Data Structures

Linked List

Read Full Article

Deletion in singly linked list at the end

There are two scenarios in which, a node is deleted from the end of the linked list.

There is only one node in the list and that needs to be deleted.
There are more than one node in the list and the last node of the list will be deleted.

C Exercises: Delete the last node of Singly Linked List

Last update on December 20 2021 09:10:22 (UTC/GMT +8 hours)

Logic to Delete the Last Node of a Linked List

If head points to NULL, return. The linked list is empty – there is no node.
If the first node points to NULL – there is only one node in the linked list, delete the first node and assign NULL to head.
Point prev to first node and cur to second node.
Keep moving prev and cur (prev = prev->next, cur = cur->next) until cur->next is NULL.
If cur->next is NULL, set prev->next equals to NULL and delete cur.

Read also: Delete any node from a linked list.

Read also: Delete the first node of a linked list.