A LeetCode Daily Series — Day 76

In this article, we’ll dive into the problem of removing the Nth node from the end of a linked list. We’ll explore both a brute force approach and a more efficient solution to solve this problem. Let’s get started!

Remove Nth Node From End Of List - LeetCode leetcode.com

Can you solve this real interview question? Remove Nth Node From End Of List

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

A LeetCode Daily Series — Introduction | Ritesh Shakya riteshakya.com.np

Hey everyone, I’m excited to announce that I’m embarking on a journey to conquer LeetCode!

Understanding the Problem

Given the head of a linked list, we need to remove the Nth node from the end of the list and return its head. Here’s what the problem looks like with a few examples:

Example 1:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1
Output: []

Example 3:

Input: head = [1,2], n = 1
Output: [1]

Brute Force Approach

The brute force approach involves two passes through the linked list. In the first pass, we determine the length of the list. In the second pass, we remove the Nth node from the end by adjusting pointers.

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    temp = head
    count = 0

    while temp:
        count += 1
        temp = temp.next

    temp = head
    prev = None

    for x in range((count - n)):
        prev = temp
        temp = temp.next

    if prev == None:
        head = head.next
        return head
    else:
        prev.next = prev.next.next
        return head

Explanation

1. Initialization: We create a dummy node pointing to the head of the list. This helps in handling edge cases where the head itself needs to be removed.
2. First Pass: We iterate through the list to count the total number of nodes.
3. Second Pass: We iterate through the list again to reach the node just before the one we need to remove.
4. Removal: We adjust the next pointer of the previous node to skip the node to be removed.

Time Complexity: O(n), where n is the length of the linked list, due to the two passes through the list.

Space Complexity: O(1), since we are using a constant amount of extra space.

Using Efficient Approach (Two Pointers)

The two-pointer approach allows us to solve the problem in a single pass through the list. We use two pointers: one starts ahead by n nodes, and then both pointers move together until the first pointer reaches the end of the list.

def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    left = dummy
    right = head

    while n > 0 and right:
        right = right.next
        n -= 1

    while right:
        left = left.next
        right = right.next

    left.next = left.next.next

    return dummy.next

Explanation

1. Initialization: We create a dummy node pointing to the head of the list. We also initialize two pointers, left and right.
2. Advance Right Pointer: We move the right pointer n nodes ahead.
3. Move Both Pointers: We move both pointers until the right pointer reaches the end of the list. This ensures that the left node reaches the node just before the one we need to remove.
4. Removal: We adjust the next pointer of the left pointer to skip the node to be removed.

Time Complexity: O(n), where n is the length of the linked list, due to the two passes through the list.

Space Complexity: O(1), since we are using a constant amount of extra space.

Conclusion

In this article, we explored the problem of removing the Nth node from the end of a linked list. We discussed a brute force approach that involves two passes through the list and an efficient two-pointer approach that solves the problem in a single pass.

Understanding these methods enhances your problem-solving skills and prepares you for tackling similar challenges in coding interviews and competitions.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.

Next Articles in the Series

A LeetCode Daily Series — Day 77 | Ritesh Shakya riteshakya.com.np

Today’s problem is called "Sort List"