Deleting Linked List Nodes, thesarfo

Delete the head — update the head pointer to point to the second node:

public Node deleteHead(Node head){
    if(head == null) return null; // empty list
    head = head.next;

    return head;
}

In C++ you’ll have to free(temp) to release the old head before returning; in Java the GC handles it automatically.

Delete the tail — walk to the second-to-last node and null out its next:

public Node removeTail(Node head){
    if(head == null || head.next == null){ // list is empty / contains only 1 element
        return null;
    }

    Node temp = head;

    while(temp.next.next != null){
        temp = temp.next;
    }
    temp.next = null;

    return head;
}

Delete the kth node — there are a few scenarios to consider: k greater than the list length, k being the head, k being the tail, or k being a middle node.

public Node deleteKthNode(Node head, int k){
    if(head == null) return head; // if the LL is empty

    if(k == 1){ // delete head of the LL
        head = head.next;
        return head;
    }

    Node temp = head;
    int count = 1;

    // Move to the (k-1)th node
    while(temp != null && count < k - 1){
        temp = temp.next;
        count++;
    }

    // If k is greater than the length of the list
    if(temp == null || temp.next == null){
        return head; // Do nothing, invalid k
    }

    // Skip the kth node
    temp.next = temp.next.next;

    return head;
}