Delete a node from the Linked List at any given position

Given a singly linked list, the task is to delete a node from the list at any given position. The function should handle all cases efficiently, including deleting the first node, deleting a node from the middle, and deleting the last node.

Input-Output Examples

Example 1: Delete from the beginning

  • Input:
    • List: 1 -> 2 -> 3 -> NULL
    • Position: 0
  • Output: 2 -> 3 -> NULL

Example 2: Delete from any given position

  • Input:
    • List: 1 -> 2 -> 3 -> 4 -> NULL
    • Position: 2
  • Output: 1 -> 2 -> 4 -> NULL

Example 3: Delete from the end

  • Input:
    • List: 1 -> 2 -> 3 -> NULL
    • Position: 2
  • Output: 1 -> 2 -> NULL

Approach:

To delete a node from the linked list, we need to handle three cases: deleting the first node, deleting a node from any given position, and deleting the last node. We will use a single function that takes the head of the list and the position of the node to be deleted as parameters.

Steps to implement:

  1. Delete the First Node:
    • If the position is 0, update the head to the next node and delete the original head.
  2. Delete from Any Given Position:
    • Traverse the list to find the node just before the one to be deleted.
    • Update the next pointer of the previous node to skip the node to be deleted.
    • Delete the node.
  3. Delete the Last Node:
    • This is handled naturally by the general approach since the last node's next pointer will be NULL.

C++ Program to delete a node from the Linked List at any given position

cpp
#include <iostream>
using namespace std;

// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// Function to delete a node at the specified position
ListNode* deleteAtPosition(ListNode* head, int position) {
    // If linked list is empty
    if (head == NULL) return NULL;
    
    ListNode* temp = head;

    // If head needs to be removed
    if (position == 0) {
        head = temp->next;
        delete temp;
        return head;
    }

    // Find previous node of the node to be deleted
    for (int i = 0; temp != NULL && i < position - 1; i++) {
        temp = temp->next;
    }

    // If position is more than number of nodes
    if (temp == NULL || temp->next == NULL) return head;

    // Node temp->next is the node to be deleted
    ListNode* next = temp->next->next;

    delete temp->next; // Free memory

    temp->next = next; // Unlink the deleted node from the list

    return head;
}

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

int main() {
    // Creating a linked list: 1 -> 2 -> 3 -> 4 -> NULL
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);

    // Delete from the beginning
    head = deleteAtPosition(head, 0);
    cout << "After deleting at position 0: ";
    printList(head);

    // Delete from a given position
    head = deleteAtPosition(head, 1);
    cout << "After deleting at position 1: ";
    printList(head);

    // Delete from the end
    head = deleteAtPosition(head, 2); // Now the last node is at position 2
    cout << "After deleting at position 2: ";
    printList(head);

    return 0;
}

Java Program to delete a node from the Linked List at any given position

java
// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; next = null; }
}

public class Main {
    // Function to delete a node at the specified position
    public static ListNode deleteAtPosition(ListNode head, int position) {
        // If linked list is empty
        if (head == null) return null;
        
        ListNode temp = head;

        // If head needs to be removed
        if (position == 0) {
            head = temp.next;
            return head;
        }

        // Find previous node of the node to be deleted
        for (int i = 0; temp != null && i < position - 1; i++) {
            temp = temp.next;
        }

        // If position is more than number of nodes
        if (temp == null || temp.next == null) return head;

        // Node temp.next is the node to be deleted
        ListNode next = temp.next.next;

        temp.next = next; // Unlink the deleted node from the list

        return head;
    }
    
    // Helper function to print the linked list
    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val + " -> ");
            head = head.next;
        }
        System.out.println("NULL");
    }

    public static void main(String[] args) {
        // Creating a linked list: 1 -> 2 -> 3 -> 4 -> NULL
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);

        // Delete from the beginning
        head = deleteAtPosition(head, 0);
        System.out.print("After deleting at position 0: ");
        printList(head);

        // Delete from a given position
        head = deleteAtPosition(head, 1);
        System.out.print("After deleting at position 1: ");
        printList(head);

        // Delete from the end
        head = deleteAtPosition(head, 2); // Now the last node is at position 2
        System.out.print("After deleting at position 2: ");
        printList(head);
    }
}

Python Program to delete a node from the Linked List at any given position

python
# Definition for singly-linked list.
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

# Function to delete a node at the specified position
def delete_at_position(head, position):
    # If linked list is empty
    if head is None:
        return None
    
    temp = head

    # If head needs to be removed
    if position == 0:
        head = temp.next
        temp = None
        return head

    # Find previous node of the node to be deleted
    for _ in range(position - 1):
        temp = temp.next
        if temp is None:
            break

    # If position is more than number of nodes
    if temp is None or temp.next is None:
        return head

    # Node temp.next is the node to be deleted
    next = temp.next.next

    temp.next = None
    temp.next = next  # Unlink the deleted node from the list

    return head

# Helper function to print the linked list
def print_list(head):
    while head:
        print(head.val, end=" -> ")
        head = head.next
    print("NULL")

# Creating a linked list: 1 -> 2 -> 3 -> 4 -> NULL
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)

# Delete from the beginning
head = delete_at_position(head, 0)
print("After deleting at position 0:", end=" ")
print_list(head)

# Delete from a given position
head = delete_at_position(head, 1)
print("After deleting at position 1:", end=" ")
print_list(head)

# Delete from the end
head = delete_at_position(head, 2)  # Now the last node is at position 2
print("After deleting at position 2:", end=" ")
print_list(head)

DSA

5860

100

Related Articles