Deletion of the tail of LL

Linked-List Fundamentals (Single LL) Easy

Given the head of a singly linked list, delete the tail of the linked list and return the head of the modified list.

The tail is the last node of the linked list.

Examples:

Input: head -> 1 -> 2 -> 3

Output: head -> 1 -> 2

Explanation: The last node was removed.

Input: head -> 1

Output: head

Explanation: Note that the value of head is null here.

Input: head -> 7 -> 8

Constraints

1 <= number of nodes in the Linked List <= 1000
0 <= ListNode.val <= 100

Hints

If the list is empty (head == None), return None. If there is only one node (head.next == None), removing the tail leaves an empty list, so return None.
Traverse to the last node (tail), which is the node where next == None. Update the second last node’s next = None to remove the tail. Return the updated head of the list.

Company Tags

McKinsey & Company ARM Oracle Bloomberg Goldman Sachs Salesforce Texas Instruments IBM Databricks Riot Games Ubisoft Stripe PwC Red Hat Flipkart DoorDash NVIDIA JPMorgan Chase Philips Healthcare Micron Technology Dropbox Broadcom Airbnb Western Digital Johnson & Johnson TCS Cognizant Accenture Infosys Capgemini Wipro

Editorial

Intuition:

Update the linked list by pointing the second-to-last node to null. Iterate through the list until reaching this node, then set its next pointer to null. This will remove the last node from the list. In C++, remember to free the memory occupied by the last node to avoid memory leaks.

Approach:

Initialize a pointer to the head of the list and iterate to the second-to-last node, which will become the new tail.
Free the memory occupied by the last node. In languages with automatic garbage collection (e.g., Java, Python, JavaScript), this step is handled automatically.
Set the next pointer of the new tail (second-to-last node) to null to update the linked list.

Edge cases:

If the input linked list is empty, return null.
If there is only one node in the list, delete that node and return null.

Dry Run:

Solution:

#include <bits/stdc++.h>
using namespace std;

// Node structure
struct ListNode {
    int val;
    ListNode *next;
    ListNode(): val(0), next(nullptr) {}
    ListNode(int data1): val(data1), next(nullptr) {}
    ListNode(int data1, ListNode *next1): val(data1), next(next1) {}
};

class Solution {
public:
    // Function to delete the tail node of linked list 
    ListNode* deleteTail(ListNode* head) {
        
        // If the list is empty or has only one node
        if (head == NULL || head->next == NULL)
            return NULL; // Return NULL
        
        // Temporary pointer
        ListNode* 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 head of modified list
        return head;
    }
};

// Function to print the linked list
void printList(ListNode* head) {
    ListNode* current = head;
    while (current != nullptr) {
        cout << current->val << " ";
        current = current->next;
    }
    cout << endl;
}

// Function to insert a new node at the beginning of the linked list
ListNode* insertAtHead(ListNode* head, int data) {
    ListNode* newNode = new ListNode(data);
    newNode->next = head;
    head = newNode;
    return head;
}

int main() {
    // Create a linked list
    ListNode* head = nullptr;
    head = insertAtHead(head, 3);
    head = insertAtHead(head, 2);
    head = insertAtHead(head, 1);

    cout << "Original list: ";
    printList(head);
    
    // Creating an instance of Solution Class
    Solution sol;
    
    // Function call to delete the tail node
    head = sol.deleteTail(head);

    cout << "List after deleting head: ";
    printList(head);

    return 0;
}
class ListNode {
    int val;
    ListNode next;

    // Constructor
    ListNode() {
        this.val = 0;
        this.next = null;
    }

    ListNode(int data1) {
        this.val = data1;
        this.next = null;
    }

    ListNode(int data1, ListNode next1) {
        this.val = data1;
        this.next = next1;
    }
}

class Solution {
    // Function to delete the tail node of linked list
    public ListNode deleteTail(ListNode head) {

        // If the list is empty or has only one node
        if (head == null || head.next == null) {
            return null; // Return null
        }

        // Temporary pointer
        ListNode temp = head;

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

        // Delete the last node
        temp.next = null;

        // Return head of modified list
        return head;
    }
}

class Main {
    // Helper Function to print the linked list
    private static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }
    
    /* Helper Function to insert a new node at
    the beginning of the linked list */
    private static ListNode insertAtHead(ListNode head, int data) {
        ListNode newNode = new ListNode(data);
        newNode.next = head;
        return newNode;
    }
    
    // Main method
    public static void main(String[] args) {
        // Create a linked list
        ListNode head = null;
        head = insertAtHead(head, 3);
        head = insertAtHead(head, 2);
        head = insertAtHead(head, 1);

        System.out.println("Original list: ");
        printList(head);

        // Creating an instance of Solution class
        Solution sol = new Solution();

        // Function call to delete the tail node
        head = sol.deleteTail(head);

        System.out.println("List after deleting tail: ");
        printList(head);
    }
}
# Node structure
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    # Function to delete the tail node of linked list
    def deleteTail(self, head):
        
        # If the list is empty or has only one node
        if head is None or head.next is None:
            return None  # Return None
        
        # Temporary pointer
        temp = head
        
        '''Traverse to the second last 
        node in the list'''
        while temp.next.next is not None:
            temp = temp.next
        
        # Delete the last node
        temp.next = None
        
        # Return head of modified list
        return head

# Helper Function to print the linked list
def printList(head):
    current = head
    while current:
        print(current.val, end=" ")
        current = current.next
    print()

# Helper Function to insert a new node at 
# the beginning of the linked list
def insertAtHead(head, data):
    newNode = ListNode(data)
    newNode.next = head
    head = newNode
    return head

if __name__ == "__main__":
    # Create a linked list
    head = None
    head = insertAtHead(head, 3)
    head = insertAtHead(head, 2)
    head = insertAtHead(head, 1)

    print("Original list: ")
    printList(head)

    # Creating an instance of Solution class
    sol = Solution()

    # Function call to delete the tail node
    head = sol.deleteTail(head)

    print("List after deleting tail: ")
    printList(head)
// Node structure
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    // Function to delete the tail node of linked list 
    deleteTail(head) {
        
        // If the list is empty or has only one node
        if (head === null || head.next === null)
            return null; // Return null
        
        // Temporary pointer
        let temp = head;
        
        /*Traverse to the second last
        node in the list*/
        while (temp.next.next !== null) {
            temp = temp.next;
        }
        
        // Delete the last node
        temp.next = null;
        
        // Return head of modified list
        return head;
    }
}

// Function to print the linked list
function printList(head) {
    let current = head;
    while (current !== null) {
        process.stdout.write(current.val + " ");
        current = current.next;
    }
    console.log();
}

// Function to insert a new node at the beginning of the linked list
function insertAtHead(head, data) {
    let newNode = new ListNode(data);
    newNode.next = head;
    return newNode;
}

// Main function
let head = null;
head = insertAtHead(head, 3);
head = insertAtHead(head, 2);
head = insertAtHead(head, 1);

console.log("Original list: ");
printList(head);

// Creating an instance of Solution class
let sol = new Solution();

// Function call to delete the tail node
head = sol.deleteTail(head);

console.log("List after deleting tail: ");
printList(head);

Complexity Analysis:

Time Complexity: O(N) for traversing the linked list and updating the tail. Space Complexity: O(1) as no extra space has been used.

Code

Problem List