Delete Last Node of Linked List

Problem Statement: Given a linked list, delete the tail of the linked list and print the updated linked list.

Examples

Example 1:

Examples:

Input Format: 0->1->2

Result: 0->1

Explanation: The tail of the list is the last node. After removing the tail, and updating the linked list, this result is what we get.

Example 2:

Input Format: 12->5->8->7

Result: 12->5->8

Explanation: Again, after deleting the tail and updating the linked list, the list ends at the second last node, which is the new tail.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach:

The main intuition is to point the second last node to null to get the updated linked list. Hence, we will iterate till the second last node and make it point to NULL. This will effectively skip the last node of the list therefore, we will free up the memory being occupied by this node (Only in the case of C++).

Two edge cases to consider are:

  1. If the input linked list is empty, we return null.
  2. If there is only one node in the list, that node itself will be the tail, therefore we return null after deleting that node.

Algorithm:

  • Start by initializing a pointer to the head of the list that will be used to iterate through the linked list. Iterate up to the second last node, this node will be our new tail of the list.
  • After reaching the second-to-last node, free up the memory occupied by the former tail or the last node of the list.
    Note: In the case of languages like Java, Python, and Javascript, there is no need for the deletion of objects or nodes because these have an automatic garbage collection mechanism that automatically identifies and reclaims memory that is no longer in use.
  • Finally, point the second last node or the new tail to NULL to obtain the updated linked list.

Code:

C++ Code

// Node class for a linked list
class Node {
public:
    int data;         // Data of the node
    Node* next;       // Pointer to the next node in the list
    // Constructor for a node with both data and next node provided
    Node(int data1, Node* next1) {
        data = data1;
        next = next1;
    }
    // Constructor for a node with only data provided, next initialized to nullptr
    Node(int data1) {
        data = data1;
        next = nullptr;
    }
};
// Function to print the linked list starting from the given head
void printLL(Node* head) {
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}
// Function to delete the tail node of a linked list and return the new head
Node* deleteTail(Node* head) {
    // If the list is empty or has only one node, return NULL
    if (head == NULL || head->next == NULL)
        return NULL;
    // Initialize a temporary pointer to traverse the list
    Node* temp = head;
    // Traverse to the second last node in the list
    while (temp->next->next != NULL) {
        temp = temp->next;
    }
    // Delete the last node
    delete temp->next;
    // Set the next of the second last node to nullptr, effectively removing the last node
    temp->next = nullptr;
    // Return the head of the modified list
    return head;
}
int main() {
    // Initialize a vector with values for the linked list
    vector<int> arr = {12, 5, 8, 7};
    // Create a linked list with the values from the vector
    Node* head = new Node(arr[0]);
    head->next = new Node(arr[1]);
    head->next->next = new Node(arr[2]);
    head->next->next->next = new Node(arr[3]);
    // Call the deleteTail function to delete the last node
    head = deleteTail(head);
    // Print the linked list after deletion
    printLL(head);
}

Output: 12 5 8

Time Complexity: O(N) for traversing the linked list and updating the tail.

Space Complexity: O(1), as we have not used any extra space.

Java Code

// Node class definition
class Node {
    int data;
    Node next;
    // Constructor with both data and next pointer
    Node(int data1, Node next1) {
        this.data = data1;
        this.next = next1;
    }
    // Constructor with only data (next pointer set to null)
    Node(int data1) {
        this.data = data1;
        this.next = null;
    }
}
// LinkedList class
public class LinkedList {
    // Function to delete the tail of the linked list
    private static Node deleteTail(Node head) {
        // Check if the linked list is empty or has only one node
        if (head == null || head.next == null)
            return null;
        // Create a temporary pointer for traversal
        Node temp = head;
        // Traverse the list until the second-to-last node
        while (temp.next.next != null) {
            temp = temp.next;
        }
        // Nullify the connection from the second-to-last node to delete the last node
        temp.next = null;
        // Return the updated head of the linked list
        return head;
    }
    // Function to print the linked list
    private static void printLL(Node head) {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
    }
    // Main method
    public static void main(String[] args) {
        // Initialize an array with integer values
        int[] arr = {2, 5, 8, 7};
        // Create the linked list with nodes initialized with array values
        Node head = new Node(arr[0]);
        head.next = new Node(arr[1]);
        head.next.next = new Node(arr[2]);
        head.next.next.next = new Node(arr[3]);
        // Delete the tail of the linked list
        head = deleteTail(head);
        // Print the modified linked list
        printLL(head);
    }
}

Output: 12 5 8

Time Complexity: O(N) for traversing the linked list and updating the tail.

Space Complexity: O(1), as we have not used any extra space.

Python Code

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

# Function to delete the tail of the linked list
def delete_tail(head):
    # Check if the linked list is empty or has only one node
    if head is None or head.next is None:
        return None

    # Create a temporary pointer for traversal
    temp = head

    # Traverse the list until the second-to-last node
    while temp.next.next is not None:
        temp = temp.next

    # Nullify the connection from the second-to-last node to delete the last node
    temp.next = None

    # Return the updated head of the linked list
    return head

# Function to print the linked list
def print_ll(head):
    while head is not None:
        print(head.data, end=" ")
        head = head.next

# Main function
if __name__ == "__main__":
    # Initialize an array with integer values
    arr = [2, 5, 8, 7]

    # Create the linked list with nodes initialized with array values
    head = Node(arr[0])
    head.next = Node(arr[1])
    head.next.next = Node(arr[2])
    head.next.next.next = Node(arr[3])

    # Delete the tail of the linked list
    head = delete_tail(head)

    # Print the modified linked list
    print_ll(head)

Output: 12 5 8

Time Complexity: O(N) for traversing the linked list and updating the tail.

Space Complexity: O(1), as we have not used any extra space.

JavaScript Code

// Node class definition
class Node {
    constructor(data, nextNode = null) {
        this.data = data;
        this.next = nextNode;
}

// Function to delete the tail of the linked list
function deleteTail(head) {
    // Check if the linked list is empty or has only one node
    if (head === null || head.next === null) {
        return null;
    }

    // Create a temporary pointer for traversal
    let temp = head;

    // Traverse the list until the second-to-last node
    while (temp.next.next !== null) {
        temp = temp.next;
    }

    // Nullify the connection from the second-to-last node to delete the last node
    temp.next = null;

    // Return the updated head of the linked list
    return head;
}

// Function to print the linked list
function printLL(head) {
    while (head !== null) {
        console.log(head.data + " ");
        head = head.next;
    }
}

// Main function
function main() {
    // Initialize an array with integer values
    const arr = [2, 5, 8, 7];

    // Create the linked list with nodes initialized with array values
    let head = new Node(arr[0]);
    head.next = new Node(arr[1]);
    head.next.next = new Node(arr[2]);
    head.next.next.next = new Node(arr[3]);

    // Delete the tail of the linked list
    head = deleteTail(head);

    // Print the modified linked list
    printLL(head);
}

// Call the main function
main();

Output: 12 5 8

Time Complexity: O(N) for traversing the linked list and updating the tail.

Space Complexity: O(1), as we have not used any extra space.

In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.

Special thanks to Neerav Sethi for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article