Recursive function to delete k-th node from linked list

A Linked List is a linear collection of data elements that is a chain of nodes where each node is made up of two parts: data and reference pointer. The data is the value of the node and the reference pointer points to the next node ahead. The first node is called the Head node. Here is an example of 3 nodes in a Linked List:

Here, we will see how to delete a node if the position of that node is given. Let's first see the input and output and then go with the algorithm:

Node with value 7 at position 3 is deleted.

Node with value 9 at position 2 is deleted.

There are many ways to go with this algorithm. Here, we will see the recursive approach to implement the algorithm.

Let's consider the Linked List is:

We have to delete the node at position 3 that the node with value 4. Our final list should be like 18->9->20.

Now, read the further explanation carefully to understand the working. So, pos = 3 and we will assign a pointer at the head node. What we will do is, we will recursively decrement the value of pos till it reaches pos == 1. and with this, we will make the pointer point to the next node ahead. What we will achieve from this is, when pos will reach to 1, at that time the pointer will be pointing to the node which we want to delete. Let's see how:

As said above, we will recursively decrement the value of pos and similarly, the pointer will point to the node ahead. We can see when the pos reaches 1, the pointer is at the node which we want to delete. Now what we can do is, we will return the next node of the pointer that is pointer.next. As this is a recursive function, the pointer.next will be returned to the previous node that is the node with value 9 and then again the node with value 9 will be returned to the node with value 18. To simplify what is said in the previous line, look at the pictorial representation:

Ler's see the implementation of the code in Python:

class Node(object):
    def __init__(self, data):
        self.data = data
        self.next = None


def del_node(pointer, pos):

    if pointer is None:  # if the list is empty(there is no node)
        return None
    
    if pos < 1:  # if position input is not valid
        return pointer

    if pos == 1:  # the base case of recursion where pos reaches 1
        return pointer.next

    pointer.next = del_node(pointer.next, pos - 1)
    return pointer


# build a linked list
def push_ele(head, data):
    node = Node(0)
    node.data = data
    node.next = head
    head = node
    return head


# print the linked list
def printList(head):
    while (head != None):
        print(head.data, end="->")
        head = head.next

    print()


# Driver Code
head = None

head = push_ele(head, 20)
head = push_ele(head, 4)
head = push_ele(head, 9)
head = push_ele(head, 18)
# 18->9->4->20

printList(head)

pos = 3
head = del_node(head, pos)
print(f"List after deleting node at position {pos}")
printList(head)

Here, first, a Linked List is made with the function push_ele() and printed with the help of function printList(). We have to concentrate on the function del_node().

1. del_node() takes two argument:
   
   1. reference to the head of the list - pointer
      
   2. position at which the element is to be deleted from the list - pos
2. First it checks if the List is None, if yes, return None
3. Then it checks if the value of position that is pos is valid, if not, return the head reference(pointer)
4. Then, as discussed the function will have a base condition where we want to stop the recursion that is pos==1.
5. Then, through the command del_node(pointer.next, pos - 1) we recursively decrement the value of pos and the pointer will keep pointing the further node ahead.
6. When pos==1, we return pointer.next to the previous node who recursively called the function del_node(). For our above example, return pointer.next will run two times as explained with the crooked green arrows in the image above the code implementation.
7. At last, we will return pointer that will be pointing to the head of the modified Linked List.