Delete Tail of DLL

Linked-List Fundamentals (Doubly LL) Easy

Given the head of a doubly linked list, remove the node at 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 node with value 3 was removed.

Input: head -> 7

Output: head

Explanation: Note that the head has null value after the removal.

Input: head -> 2 <-> 4

Constraints

n == Number of nodes in the linked list
1 <= n <= 100
0 <= ListNode.val <= 100

Hints

If the list is empty (head is None), return None immediately, as there is nothing to delete. If the list contains only one node (head.next is None), deleting the tail means returning an empty list (None).
Use a pointer to traverse the list starting from the head. Stop when the pointer reaches the second-to-last node, i.e., when the next pointer of the current node points to the tail (node where next is None).

Company Tags

OYO Rooms McKinsey & Company Snowflake Ubisoft Morgan Stanley HCL Technologies Freshworks ARM Flipkart Visa Bain & Company Deloitte Siemens Healthineers Rockstar Games Reddit Airbnb Zomato Dropbox KPMG Shopify Seagate Technology Bungie Zoho Splunk Philips Healthcare TCS Cognizant Accenture Infosys Capgemini Wipro

Editorial

Intuition:

Update the linkage between its last node and its second last node. As a doubly linked list is bidirectional, set the second last node's next pointer and the last node's back pointer to null. Then,return the head as the result.

Approach:

Start at the head of the list.
Iterate through the list until the last node (tail) is reached.
Find the second-to-last node (prev) using the tail's back pointer.
Set the next pointer of the prev node to null.
Set the back pointer of the tail node to null.
Return the head of the list.

Note: In C++, explicitly delete the last node to free memory. In Java, garbage collection handles this.

Dry Run:

Solution:

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

// Definition of doubly linked list
struct ListNode
{
    int val;
    ListNode *next;
    ListNode *prev;
    ListNode()
    {
        val = 0;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1)
    {
        val = data1;
        next = NULL;
        prev = NULL;
    }
    ListNode(int data1, ListNode *next1, ListNode *prev1)
    {
        val = data1;
        next = next1;
        prev = prev1;
    }
};

// Solution class
class Solution {
public:
    // Function to delete the tail of a doubly linked list 
    ListNode* deleteTail(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return nullptr;  
        }
        
        // Navigate to the tail of the linked list
        ListNode* tail = head;
        while (tail->next != nullptr) 
            tail = tail->next; 
        
        // Update the pointers
        ListNode* newTail = tail->prev;
        newTail->next = nullptr;
        tail->prev = nullptr;
        
        // Free memory 
        delete tail;  
        
        return head; // Return head of modified list
    }
};

// Helper Function to convert an array to a doubly linked list
ListNode* arrayToLinkedList(vector<int> &nums) {
    // If array is empty, return nullptr
    if (nums.empty()) return nullptr; 

    // Create head node with first element of the array
    ListNode* head = new ListNode(nums[0]); 
    // Initialize 'prev' to the head node
    ListNode* prev = head;             

    for (int i=1; i < nums.size(); i++) {
        // Create a new node 
        ListNode* temp = new ListNode(nums[i], nullptr, prev);
        // Update 'next' pointer
        prev->next = temp;    
        // Move 'prev' to newly created node
        prev = temp;         
    }
    
    // Return head
    return head;  
}

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

int main() {
    vector<int> nums = {1, 2, 3, 4, 5};
    
    // Creating the doubly linked list from given array
    ListNode* head = arrayToLinkedList(nums);
    
    // Print the Original list 
    cout << "Original List: ";
    printLL(head);
    
    // Create an instance of Solution class 
    Solution sol;
    
    // Function call to delete the tail of the doubly linked list
    head = sol.deleteTail(head);
    
    // Print the Modified list
    cout << "Modified list: ";
    printLL(head);

    return 0;
}
// Definition of doubly linked list
class ListNode {
    int val;
    ListNode next;
    ListNode prev;

    ListNode() {
        val = 0;
        next = null;
        prev = null;
    }

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

    ListNode(int data1, ListNode next1, ListNode prev1) {
        val = data1;
        next = next1;
        prev = prev1;
    }
}

// Solution class
class Solution {
    // Function to delete the tail of a doubly linked list
    public ListNode deleteTail(ListNode head) {
        if (head == null || head.next == null) {
            return null;  
        }
        
        // Navigate to the tail of the linked list
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
        
        // Update the pointers
        ListNode newTail = tail.prev;
        newTail.next = null;
        tail.prev = null;
        
        // Return head of modified list
        return head;
    }
}

// Main class
class Main {
    // Helper Function to convert an array to a doubly linked list
    private static ListNode arrayToLinkedList(int[] nums) {
        // If array is empty, return null
        if (nums.length == 0) return null;

        // Create head node with first element of the array
        ListNode head = new ListNode(nums[0]);
        // Initialize 'prev' to the head node
        ListNode prev = head;

        for (int i = 1; i < nums.length; i++) {
            // Create a new node
            ListNode temp = new ListNode(nums[i], null, prev);
            // Update 'next' pointer
            prev.next = temp;
            // Move 'prev' to newly created node
            prev = temp;
        }

        // Return head
        return head;
    }

    // Helper Function to print the linked list
    private static void printLL(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " ");
            head = head.next;
        }
        System.out.println();
    }
    
    // main method
    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5};

        // Creating the doubly linked list from given array
        ListNode head = arrayToLinkedList(nums);

        // Print the Original list
        System.out.print("Original List: ");
        printLL(head);

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

        // Function call to delete the tail of the doubly linked list
        head = sol.deleteTail(head);

        // Print the Modified list
        System.out.print("Modified list: ");
        printLL(head);
    }
}
# Definition of doubly linked list
class ListNode:
    def __init__(self, data1=0, next1=None, prev1=None):
        self.val = data1
        self.next = next1
        self.prev = prev1

# Solution class
class Solution:
    # Function to delete the tail of a doubly linked list
    def deleteTail(self, head):
        if head is None or head.next is None:
            return None  # Return None if list is empty or has only one node
        
        # Navigate to the tail of the linked list
        tail = head
        while tail.next is not None:
            tail = tail.next
        
        # Update the pointers
        newTail = tail.prev
        newTail.next = None
        tail.prev = None

        # Return head of modified list
        return head

# Helper Function to convert an array to a doubly linked list
def arrayToLinkedList(nums):
    # If array is empty, return None
    if not nums:
        return None

    # Create head node with first element of the array
    head = ListNode(nums[0])
    # Initialize 'prev' to the head node
    prev = head

    for i in range(1, len(nums)):
        # Create a new node
        temp = ListNode(nums[i], None, prev)
        # Update 'next' pointer
        prev.next = temp
        # Move 'prev' to newly created node
        prev = temp

    # Return head
    return head

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

if __name__ == "__main__":
    nums = [1, 2, 3, 4, 5]

    # Creating the doubly linked list from given array
    head = arrayToLinkedList(nums)

    # Print the Original list
    print("Original List: ", end="")
    printLL(head)

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

    # Function call to delete the tail of the doubly linked list
    head = sol.deleteTail(head)

    # Print the Modified list
    print("Modified list: ", end="")
    printLL(head)
// Definition of doubly linked list
class ListNode {
    constructor(data1 = 0, next1 = null, prev1 = null) {
        this.val = data1;
        this.next = next1;
        this.prev = prev1;
    }
}

// Solution class
class Solution {
    // Function to delete the tail of a doubly linked list
    deleteTail(head) {
        if (head === null || head.next === null) {
            return null;  // Return null if list is empty or has one node
        }
        
        // Navigate to the tail of the linked list
        let tail = head;
        while (tail.next !== null) {
            tail = tail.next;
        }
        
        // Update the pointers
        let newTail = tail.prev;
        newTail.next = null;
        tail.prev = null;

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

// Helper Function to convert an array to a doubly linked list
function arrayToLinkedList(nums) {
    // If array is empty, return null
    if (nums.length === 0) return null;

    // Create head node with first element of the array
    let head = new ListNode(nums[0]);
    // Initialize 'prev' to the head node
    let prev = head;

    for (let i = 1; i < nums.length; i++) {
        // Create a new node
        let temp = new ListNode(nums[i], null, prev);
        // Update 'next' pointer
        prev.next = temp;
        // Move 'prev' to newly created node
        prev = temp;
    }

    // Return head
    return head;
}

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

const main = () => {
    const nums = [1, 2, 3, 4, 5];

    // Creating the doubly linked list from given array
    let head = arrayToLinkedList(nums);

    // Print the Original list
    console.log("Original List: ");
    printLL(head);

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

    // Function call to delete the tail of the doubly linked list
    head = sol.deleteTail(head);

    // Print the Modified list
    console.log("Modified list: ");
    printLL(head);
}

main();

Complexity Analysis:

Time Complexity: O(1) as it only involves updating of references. Space Complexity: O(1) as no extra space used.

Code

Problem List