Deletion of the head of LL

Linked-List Fundamentals (Single LL) Easy

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

The head is the first node of the linked list.

Please note that this section might seem a bit difficult without prior knowledge on what linkedlist is, we will soon try to add basics concepts for your ease! If you know the concepts already please go ahead to give a shot to the problem. Cheers!

Examples:

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

Output: head -> 2 -> 3

Explanation: The first node was removed.

Input: head -> 1

Output: head

Explanation: Note that the head of the linked list gets changed.

Input: head -> 7 -> 8

Constraints

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

Hints

Check if the list is empty (i.e., head is null or None). If true, return null or None, as there's no node to delete.
If the list contains at least one node, move the head pointer to the next node.

Company Tags

Texas Instruments Oracle Roche IBM MongoDB Riot Games eBay McKinsey & Company Morgan Stanley Pinterest Byju's Epic Systems PwC Shopify Seagate Technology Unity Technologies Stripe Target Nutanix Zoho Walmart Johnson & Johnson Chewy Flipkart DoorDash TCS Cognizant Accenture Infosys Capgemini Wipro

Editorial

Intuition:

Deleting the head node of a linked list involves changing the head pointer to point to the next node. This makes the second node the new head of the list, effectively removing the original head node.

Approach:

Set a temporary pointer to the current head of the linked list and update the head to point to the next node, effectively skipping the original head node.
The original head node is now disconnected and can be deleted to free up memory. Note that in languages with automatic garbage collection like Java, Python, and JavaScript, manual deletion is not needed.
Return the new head of the linked list, which is now the original second node.

Edge Cases:

If the input linked list is empty, we return null.
If there is only one node in the list, we return null after deleting that node.

Dry Run:

1 / 4

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 head node of the linked list
    ListNode* deleteHead(ListNode* head) {
        // If list is empty, nothing to delete
        if (head == nullptr) 
            return nullptr; 
        
        // Set temporary pointer
        ListNode* temp = head; 
        
        // Update head to the next node 
        head = head->next;  
        
        // Delete original head    
        delete temp; 
        
        // Return new head          
        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 head node
    head = sol.deleteHead(head);

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

    return 0;
}
import java.util.*;

// Node structure
class ListNode {
    int val;
    ListNode next;

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

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

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

class Solution {
    // Function to delete the head node of the linked list
    public ListNode deleteHead(ListNode head) {
        // If list is empty, nothing to delete
        if (head == null) 
            return null;

        // Set temporary pointer
        ListNode temp = head;

        // Update head to the next node 
        head = head.next;

        // Delete original head    
        temp = null;

        // Return new head          
        return head;
    }
}

class Main {
    private static void printList(ListNode head) {
        ListNode current = head;
        while (current != null) {
            System.out.print(current.val + " ");
            current = current.next;
        }
        System.out.println();
    }

    // Function to insert a new node at the beginning of the linked list
    public static ListNode insertAtHead(ListNode head, int data) {
        ListNode newNode = new ListNode(data);
        newNode.next = head;
        head = newNode;
        return head;
    }
    
    
    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.print("Original list: ");
        printList(head);
        
        // Creating an instance of Solution Class
        Solution sol = new Solution();
        
        // Function call to delete the head node
        head = sol.deleteHead(head);

        System.out.print("List after deleting head: ");
        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 head node of the linked list
    def deleteHead(self, head):
        # If list is empty, nothing to delete
        if head is None:
            return None
        
        # Set temporary pointer
        temp = head
        
        # Update head to the next node 
        head = head.next
        
        # Delete original head    
        del temp
        
        # Return new head          
        return head

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

# 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: ", end="")
    printList(head)
    
    # Creating an instance of Solution Class
    sol = Solution()
    
    # Function call to delete the head node
    head = sol.deleteHead(head)

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

class Solution {
    // Function to delete the head node of the linked list
    deleteHead(head) {
        // If list is empty, nothing to delete
        if (head === null) 
            return null;

        // Set temporary pointer
        let temp = head;

        // Update head to the next node 
        head = head.next;

        // Delete original head    
        temp = null;

        // Return new head          
        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;
    }
    process.stdout.write("\n");
}

// 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;
    head = newNode;
    return head;
}

// Main function
function main() {
    // Create a linked list
    let head = null;
    head = insertAtHead(head, 3);
    head = insertAtHead(head, 2);
    head = insertAtHead(head, 1);

    process.stdout.write("Original list: ");
    printList(head);
    
    // Creating an instance of Solution Class
    let sol = new Solution();
    
    // Function call to delete the head node
    head = sol.deleteHead(head);

    process.stdout.write("List after deleting head: ");
    printList(head);
}

// Execute the main function
main();

Complexity Analysis

Time Complexity: O(1) for updating the head of the linked list.

Space Complexity: O(1) as no extra space is used.

Code

Problem List