Data Structures and Algorithms — Linked Lists #4- Delete a node in a singly linked list

Problem Statement:

Given a singly linked list and an integer x. Delete xth node from the singly linked list.

Example 1:

Input: 1 -> 3 -> 4 
       x = 3
Output: 1 -> 3
Explanation:
After deleting the node at 3rd
position (1-base indexing), the
linked list is as 1 -> 3.

Example 2:

Input: 1 -> 5 -> 2 -> 9 
x = 2
Output: 1 -> 2 -> 9
Explanation: 
After deleting the node at 2nd
position (1-based indexing), the
linked list is as 1 -> 2 -> 9.

The task is to write a function deleteNode() which takes two arguments: the address of the head of the linked list and an integer x. The function returns the head of the modified linked list.

Note: The given integer x does not denote the data value of the linked list to be deleted. It denotes the index of the linked list.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Concept:

We have to traverse the linked list. Once we reach a node whose index matches x, the previous pointer must point to the next node.

Thus, we have to break the link between the current and previous node. Also, we must create a new link between the previous and next nodes.

Visual Representation:

Step-by-Step Approach:

• Initialize two nodes/pointers:

current: points to the current head

prev: points to null

• Initialize index as 1(as we are using 1-base indexing). This variable will keep track of the index of each node in the linked list.
• Edge case — If head is the node to be deleted: New head will point to the next node. Return the new head.
• For non-head nodes: Traverse the list until the current node is not null and the index is not equal to x.
• If the node to be deleted is found, make the next node of previous pointer point to the next node of current pointer. This is where the link between current and previous pointer is broken.
• Return the head node.

Code:

Complexity Analysis:

Time Complexity: O(N).
’N’ is the number of nodes in the linked list.

Space Complexity: O(1).

If you liked this article, please click the “clap” button 👏 a few times.

Gives me enough motivation to put out more content like this. Please share it with a friend who you think this article might help.

Follow me Varsha Das to receive my weekly articles.

Connect with me — Varsha Das | LinkedIn

Follow my Youtube channel where we discuss Data Structures & Algorithms.

Thanks for reading.

Happy learning! 😁