LINK01P13 - Editorial

editorial
, ,
1

Problem Link- Delete from any position

Problem Statement:

Deletion from any position other than front is a little different.

Approach:

The deleteNode function removes a node with a specific value from a linked list:

  • If the node to delete is the head:

    • Simply update the head pointer to the next node and delete the old head.

  • If the node is elsewhere:

    • Traverse the list until you find the node whose next node has the target value.
    • Then, skip over the target node by updating the next pointer.

Explanation of iter -> next = iter -> next -> next:

This line removes the target node by by passing it:

  • iter -> next is the node we want to remove.

  • iter -> next -> next is the node that comes after the one we want to remove.

  • By setting iter -> next = iter -> next -> next, we make the current node skip the node being deleted, linking directly to the next one. This effectively removes the target node from the list.

Time Complexity:

  • O(n) because in the worst case, you may have to traverse the entire list to find the node to delete.

Space Complexity:

  • O(1) since no additional space is used, only pointers are adjusted.