Delete head of DLL

Linked-List Fundamentals (Doubly LL) Easy

Given the head of a doubly linked list, remove the node at the head of the linked list and return the head of the modified list.

The head is the first node of the linked list.

Examples:

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

Output: head -> 2 <-> 3

Explanation: The node with value 1 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 == None), return None. If there is only one node, remove it by returning None.
Update head to point to the next node (head.next). If the new head exists, set its prev = None to break the link. Return the updated head.

Company Tags

Ernst & Young Activision Blizzard American Express PayPal Red Hat McKinsey & Company Boston Consulting Group Swiggy Epic Games Shopify MongoDB Roblox Flipkart Splunk Oracle Zoho Ubisoft Visa DoorDash Reddit Medtronic Seagate Technology Wayfair Goldman Sachs Lyft TCS Cognizant Accenture Infosys Capgemini Wipro

Editorial

Intuition:

Break the linkage of the current head to the Double Linked List, and return the next node as the new head.

Approach:

Set a pointer to the current head.
Make the next node the new head.
Remove the back pointer of the new head.
Remove the next pointer of the old head.
The new head is the result.

Note: In C++, explicitly delete the old head to free memory. In Java, Python garbage collection handles this.

Edge cases:

If the list is empty, return null.
If the list has only one node, delete it 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 delete the head of the doubly linked list
    ListNode* deleteHead(ListNode* head) {
        if (head == nullptr || head->next == nullptr) 
            return nullptr; // Return NULL 

        // Store current head as 'prev'
        ListNode* prev = head;      
        // Move 'head' to next node
        head = head->next;    

        // Set 'prev' pointer 
        head->prev = nullptr;   

        // Set 'next' pointer 
        prev->next = nullptr;  

        // Return new 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};
    
    // 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 head of the doubly linked list
    head = sol.deleteHead(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 head of the doubly linked list
    public ListNode deleteHead(ListNode head) {
        if (head == null || head.next == null)
            return null; // Return null if the list is empty or has one node
        
        // Store current head as 'prev'
        ListNode prev = head;
        // Move 'head' to next node
        head = head.next;

        // Set 'prev' pointer
        head.prev = null;

        // Set 'next' pointer
        prev.next = null;

        // Return new 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};

        // 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 head of the doubly linked list
        head = sol.deleteHead(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 head of the doubly linked list
    def deleteHead(self, head):
        if head is None or head.next is None:
            return None  # Return None if list is empty or has one node
        
        # Store current head as 'prev'
        prev = head
        # Move 'head' to next node
        head = head.next

        # Set 'prev' pointer
        head.prev = None

        # Set 'next' pointer
        prev.next = None

        # Return new 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]

    # 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 head of the doubly linked list
    head = sol.deleteHead(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 head of the doubly linked list
    deleteHead(head) {
        if (head === null || head.next === null)
            return null; // Return null if list is empty or has one node
        
        // Store current head as 'prev'
        let prev = head;
        // Move 'head' to next node
        head = head.next;

        // Set 'prev' pointer
        head.prev = null;

        // Set 'next' pointer
        prev.next = null;

        // Return new 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];

    // 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 head of the doubly linked list
    head = sol.deleteHead(head);

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

main();

Complexity Analysis:

Time Complexity: O(1) because removing the head node from a doubly linked list is a constant-time operation. It's independent of the list's size, as it involves updating references to the head and the new head. Space Complexity: O(1) as no extra space is used.

Code

Problem List