The Problem:

In this problem, we are given a linked list and an index n. We have to remove the n-th node from the back of the linked list for example given linked list = 1->2->3->4->5 and n = 2, we would have to return the head of list 1->2->3->5

Before we begin trying to figure out a solution for this problem, let’s first revisit an important concepts Linked List and Recursion.

Understanding Recursion:

Recursion is essentially a function calling itself. It is frequently used to solve problems that can be divided into smaller, similar sub-problems and can be very useful in dynamic programming. To understand recursion, it can be helpful to break it down into 3 parts:

1. Base Condition: This condition prevents the recursive function from calling itself infinitely.
2. Recursive Call: This is responsible for calling the recursive function itself.
3. Small Calculation: This step, which can come before or after the Recursive Call, is responsible for performing some calculation that we need for the recursive function or for returning some result after a recursive call has been completed.

A recursive tree is a visual representation of the recursive calls made by a function. It can be very helpful in understanding how recursion works and in analyzing the time and space complexity of recursive algorithms.

Understanding Linked List:

A linked list is a linear data structure that consists of a sequence of nodes, each containing data and a reference to the next node in the list. It is often used as an alternative to arrays, as it can be more efficient in certain operations such as insertion and deletion.

To understand linked lists, it can be helpful to break it down into 3 parts:

1. Nodes: Each node in a linked list contains some data and a reference to the next node in the list.
2. Head: The head of a linked list is the first node in the list. It is used as the starting point for many operations on the list.
3. Traversal: Traversing a linked list involves starting at the head and following the references from one node to the next until the desired node is reached or the end of the list is reached.

Linked lists can be very useful in solving problems that involve dynamic data structures, as they allow for efficient insertion and deletion of elements. They can also be used in combination with other data structures, such as stacks and queues, to solve more complex problems.

Intuition & Algorithm:

The first step is to calculate the size of the linked list using the, we defined a function say get_size which takes in the head of the linked list and a length variable initialized to 1. The function increments the length variable and calls itself recursively with the next node until it reaches the end of the linked list, at which point it returns the length.

Once we have the length of the linked list, we can use another recursive function, say helper to remove the nth node from the end. This function takes in the head of the linked list, a counter variable initialized to 0, the length of the linked list, and n. The function increments the counter variable and calls itself recursively with the next node. When it reaches the node that is n nodes away from the end (determined by checking if (length - counter) == n - 1), it removes that node by updating its value and next pointer to those of its next node. If it is the last node, it returns None. Otherwise, it returns the head.

This ensures that we will always be able to remove the given n-th node from the back of a linked list.

Summary of Solution

Get the size of the linked list, through recursion. Then traverse through the linked list knowing its length, the index n and update a counter when you reach n nodes away from end i.e. length - counter == n - 1 then replace the node with the next node.

Code

This can be translated to code in the following way:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        def get_size(head, length):
            if head == None or head.next == None:
                return length
            length += 1
            return get_size(head.next, length)

        def helper(head,counter, length, n):
            if head == None:
                return head
            counter += 1
            head.next = helper(head.next, counter, length, n)
            if (length - counter) == n - 1:
                if head.next:
                    head.val = head.next.val
                    head.next = head.next.next
                    return head
                else:
                    return None
            return head
        length = 1
        length = get_size(head,length)
        return helper(head,0,length,n)

• Time Complexity O(n)
• Space Complexity O(n)

The time complexity of this solution is O(n) This is because the function needs to traverse the linked lists to calculate the size and then it traverses again to get to the n-th node. Time taken for this operation would be proportional to the size of the linked list.

Space complexity is O(n) because of recursion call stack.

This approach is simple and efficient, making it a good solution to this problem.

I hope you enjoyed this post. Stay tuned for daily LeetCode blog posts!