Delete Kth Element of DLL

Linked-List Fundamentals (Doubly LL) Easy Go Ad-Free - ₹20/mo

Given the head of a doubly linked list and an integer k, remove the node at the k^th position of the linked list and return the head of the modified list.

Examples:

Input: head -> 2 <-> 5 <-> 7 <-> 9, k = 2

Output: head -> 2 <-> 7 <-> 9

Explanation: The node with value 5 was removed.

Input: head -> 2 <-> 5 <-> 7, k = 1

Output: head -> 5 <-> 7

Explanation: The node with value 2 was removed, note that the head was modified.

Input: head -> 2 <-> 5 <-> 7, k = 3

Constraints

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

Hints

If k=1: Update the head pointer to head.next to remove the head node. For k>1: Traverse the list to find the (k−1)-th node (node preceding the target node).
Use a pointer to traverse the list and keep a count of the current position. Stop when the pointer reaches the (k−1)-th node, i.e., just before the node to be deleted.

Company Tags

Docker Square Bain & Company Activision Blizzard Zoho Airbnb Optum Rakuten Goldman Sachs Medtronic NVIDIA Western Digital Epic Systems Teladoc Health Red Hat Oracle Walmart Boston Consulting Group OYO Rooms Zomato Wayfair Roblox PwC Stripe Target TCS Cognizant Accenture Infosys Capgemini Wipro

Editorial

Intuition:

Locate the node just before the kth node by traversing the list. Then, change the pointer of this node to bypass the k-th node and connect directly to the node after it.

Approach:

Traverse the doubly linked list to find the K-th node, maintaining a counter. Use a while loop to increment the counter and move to the next node until the counter equals K. Use a temporary pointer to point to the K-th node to be deleted.
Set the previous node to the node to which the temporary pointer’s back pointer is pointing. Track the temporary pointer’s next node using the front pointer.
Update the 'next' pointer of the previous node to point to the front node.
Update the 'back' pointer of the front node to point to the back node.
Set the temporary pointer’s next and back pointers to null so it does not point to anything. This updates the doubly linked list to be one node shorter.
(C++ Only) Explicitly delete the previous head to free memory. In Java, the garbage collector automatically handles memory management for unreferenced objects.

Edge Cases:

If the input doubly linked list is empty, return null as there is nothing to delete.
If K equals 1 (deleting the first node), follow the steps to delete the head of the list.
If K equals the length of the doubly linked list, delete the tail of the list.
If the list has a single element, K can only be 1, so delete this node and return null.

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 remove the Kth element
    ListNode* deleteKthElement(ListNode* head, int k) {
        // If the list is empty, return nullptr
        if (head == nullptr) 
            return nullptr;
    
        int count = 0;
        ListNode* kNode = head;

        // Traverse the list
        while (kNode != nullptr) {
            count++;
            if (count == k) break;
            kNode = kNode->next;
        }

        // If k is larger 
        if (kNode == nullptr) return head; 
        
        // Update the pointers
        ListNode* prev = kNode->prev;
        ListNode* front = kNode->next;

        // If node to be deleted is only node in list
        if (prev == nullptr && front == nullptr) {
            delete kNode;
            return nullptr;
        }
        
        // If node to be deleted is head of list
        else if (prev == nullptr) {
            head = front;
            front->prev = nullptr;
        }
        
        // If node to be deleted is tail of list
        else if (front == nullptr) {
            prev->next = nullptr;
        }
        
        // If node to be deleted is in middle of list
        else {
            prev->next = front;
            front->prev = prev;
        }

        // Free memory of the deleted node
        delete kNode;
        
        // Return modified list head
        return head;
    }
};

// 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};
    int k = 2;
    
    // 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 kth Node of the doubly linked list
    head = sol.deleteKthElement(head, k);
    
    // 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 remove the Kth element
    public ListNode deleteKthElement(ListNode head, int k) {
        // If the list is empty, return null
        if (head == null) 
            return null;
    
        int count = 0;
        ListNode kNode = head;

        // Traverse the list
        while (kNode != null) {
            count++;
            if (count == k) break;
            kNode = kNode.next;
        }

        // If k is larger than the list size
        if (kNode == null) return head; 
        
        // Update the pointers
        ListNode prev = kNode.prev;
        ListNode front = kNode.next;

        // If node to be deleted is the only node in the list
        if (prev == null && front == null) {
            return null;
        }
        
        // If node to be deleted is head of the list
        else if (prev == null) {
            head = front;
            front.prev = null;
        }
        
        // If node to be deleted is tail of the list
        else if (front == null) {
            prev.next = null;
        }
        
        // If node to be deleted is in the middle of the list
        else {
            prev.next = front;
            front.prev = prev;
        }

        // Return modified list head
        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};
        int k = 2;

        // 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 kth Node of the doubly linked list
        head = sol.deleteKthElement(head, k);

        // 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 remove the Kth element
    def deleteKthElement(self, head, k):
        # If the list is empty, return None
        if head is None:
            return None
        
        count = 0
        kNode = head

        # Traverse the list
        while kNode is not None:
            count += 1
            if count == k:
                break
            kNode = kNode.next

        # If k is larger than the list size
        if kNode is None:
            return head

        # Update the pointers
        prev = kNode.prev
        front = kNode.next

        # If node to be deleted is the only node in the list
        if prev is None and front is None:
            return None
        
        # If node to be deleted is head of the list
        elif prev is None:
            head = front
            front.prev = None
        
        # If node to be deleted is tail of the list
        elif front is None:
            prev.next = None
        
        # If node to be deleted is in the middle of the list
        else:
            prev.next = front
            front.prev = prev

        # Return modified list head
        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]
    k = 2

    # 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 kth Node of the doubly linked list
    head = sol.deleteKthElement(head, k)

    # 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 remove the Kth element
    deleteKthElement(head, k) {
        // If the list is empty, return null
        if (head === null) 
            return null;
    
        let count = 0;
        let kNode = head;

        // Traverse the list
        while (kNode !== null) {
            count++;
            if (count === k) break;
            kNode = kNode.next;
        }

        // If k is larger than the list size
        if (kNode === null) return head; 
        
        // Update the pointers
        let prev = kNode.prev;
        let front = kNode.next;

        // If node to be deleted is the only node in the list
        if (prev === null && front === null) {
            return null;
        }
        
        // If node to be deleted is head of the list
        else if (prev === null) {
            head = front;
            front.prev = null;
        }
        
        // If node to be deleted is tail of the list
        else if (front === null) {
            prev.next = null;
        }
        
        // If node to be deleted is in the middle of the list
        else {
            prev.next = front;
            front.prev = prev;
        }

        // Return modified list head
        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];
    const k = 2;

    // 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 kth Node of the doubly linked list
    head = sol.deleteKthElement(head, k);

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

main();

Complexity Analysis:

Time Complexity: O(k) because it only involves identifying the Kth node and updating its references to delete it. Space Complexity: O(1) as no extra space is used.

Frequently Occurring Doubts

Q: What if k is greater than the length of the list?

A: During traversal, check if the k-th node exists. If the traversal ends before reaching k, return the list unchanged.

Q: How do you handle k-th node deletion when k is the last node?

A: Traverse to the second-to-last node and set its next pointer to None.

Interview Followup Questions

Q: How would you efficiently find and delete the k-th node in a frequently accessed list?

A: Maintain a count of the total number of nodes to verify k’s validity before traversing. Alternatively, maintain a pointer to the k-th node during updates.

Q: How would you adapt this approach for deleting a node with a specific value instead of the k-th node?

A: Traverse the list until the node with the specific value is found, and update the preceding node’s next pointer to skip the target node.

Notes

Your notes are automatically saved in your browser's local storage and will persist across sessions on this device.

Problem Categories