Remove Nth Node From End Of List In JavaScript (Two-Pass)

by SLV Team 58 views

Hey guys! Today, we're diving into a classic data structures and algorithms (DSA) problem: removing the Nth node from the end of a linked list. We'll be tackling this using the two-pass approach in JavaScript. This method is super common in interviews, so understanding it is crucial. Let's break it down step by step.

Understanding the Problem

Before we jump into the code, let's make sure we're all on the same page. Imagine you have a linked list, which is basically a chain of nodes where each node contains a value and a pointer to the next node. The problem asks us to remove the node that is N positions away from the end of the list.

For example, if our list is 1 -> 2 -> 3 -> 4 -> 5 and N = 2, we need to remove the second node from the end, which is 4. The resulting list should be 1 -> 2 -> 3 -> 5. Pretty straightforward, right? The tricky part is doing this efficiently, and that's where the two-pass approach comes in handy.

Why Two Passes?

The core idea behind the two-pass approach is to first determine the length of the linked list. Why do we need the length? Because knowing the length allows us to calculate the position of the Nth node from the end from the beginning of the list. Once we know the position from the beginning, removing the node becomes a much simpler task. This is a clever way to avoid using extra space, which is often a concern in coding interviews. We're aiming for an efficient solution in terms of both time and space complexity.

The Two-Pass Approach: A Step-by-Step Guide

The two-pass approach involves two main steps:

  1. First Pass: Calculate the Length of the Linked List

    • We start by traversing the entire linked list, node by node, and incrementing a counter for each node we encounter. This counter will give us the total number of nodes in the list.
    • We initialize a counter variable, usually called length or count, to 0. Then, we start from the head of the list and move through each node until we reach the end (i.e., when the next pointer of the current node is null).
    • For each node we visit, we increment the counter. By the end of this pass, the counter will hold the total length of the linked list. This is crucial information for our next step.

  2. Second Pass: Remove the Nth Node from the End

    • Now that we know the length of the list, we can calculate the position of the node to be removed from the beginning. If the list has L nodes and we want to remove the Nth node from the end, that's the (L - N + 1)th node from the beginning. However, we need to consider a slight adjustment because we'll be changing pointers, and it's easier to work with the node before the one we want to remove.
    • So, we actually need to traverse to the (L - N)th node from the beginning. This node's next pointer needs to be updated to skip over the Nth node from the end.
    • We start from the head again and move (L - N) steps. There are a couple of edge cases we need to handle here:
      • Edge Case 1: Removing the Head Node
        • If N is equal to the length of the list (N == L), it means we need to remove the head node itself. In this case, we simply update the head of the list to be the second node (i.e., head = head.next).
      • Edge Case 2: Invalid Input
        • If N is greater than the length of the list, it's an invalid input, and we might want to return the original list or throw an error.
    • If we're not removing the head node, we traverse to the (L - N)th node. Let's call this node previous. We then update previous.next to be previous.next.next, effectively removing the Nth node from the end.

JavaScript Implementation

Alright, let's translate this into JavaScript code. We'll start by defining a ListNode class to represent each node in the linked list:

class ListNode {
 constructor(val, next) {
 this.val = (val===undefined ? 0 : val)
 this.next = (next===undefined ? null : next)
 }
}

This ListNode class is a basic building block. Each node has a val (the value it holds) and a next pointer (pointing to the next node in the list). If a value or next pointer isn't provided, it defaults to 0 for the value and null for the next pointer.

Now, let's implement the removeNthFromEnd function:

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
 // First pass: Calculate the length of the linked list
 let length = 0;
 let current = head;
 while (current) {
 length++;
 current = current.next;
 }

 // Handle edge case: Removing the head node
 if (n === length) {
 return head.next;
 }

 // Second pass: Remove the Nth node from the end
 let previous = head;
 for (let i = 0; i < length - n - 1; i++) {
 previous = previous.next;
 }

 previous.next = previous.next.next;

 return head;
};

Let's walk through this code:

  1. We define the removeNthFromEnd function, which takes the head of the linked list and the integer n as input. It returns the modified linked list's head.
  2. First Pass:
    • We initialize length to 0 and current to head. current will be our pointer to traverse the list.
    • The while loop iterates through the list until current becomes null (the end of the list).
    • In each iteration, we increment length and move current to the next node.
  3. Edge Case: Removing the Head Node:
    • If n is equal to length, we're removing the head node. We simply return head.next, which effectively makes the second node the new head.
  4. Second Pass:
    • We initialize previous to head. previous will point to the node before the one we want to remove.
    • The for loop iterates length - n - 1 times. This is how we reach the node before the Nth node from the end.
    • In each iteration, we move previous to the next node.
  5. Removing the Node:
    • After the loop, previous points to the node before the one we want to remove. We update its next pointer to skip over the Nth node: previous.next = previous.next.next.
  6. Finally, we return the modified head of the list.

Example Usage

To see this in action, let's create a sample linked list and try removing a node:

// Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

// Remove the 2nd node from the end (which is 4)
const newHead = removeNthFromEnd(head, 2);

// Print the modified list: 1 -> 2 -> 3 -> 5
let current = newHead;
let result = [];
while (current) {
 result.push(current.val);
 current = current.next;
}
console.log(result.join(' -> ')); // Output: 1 -> 2 -> 3 -> 5

In this example, we create a linked list 1 -> 2 -> 3 -> 4 -> 5. We then call removeNthFromEnd(head, 2) to remove the second node from the end (which is 4). Finally, we print the modified list, which should be 1 -> 2 -> 3 -> 5.

Time and Space Complexity

Let's talk about the efficiency of this approach:

  • Time Complexity: O(N), where N is the number of nodes in the linked list. We traverse the list twice, once to calculate the length and once to remove the node.
  • Space Complexity: O(1), which means constant space. We're not using any extra data structures that scale with the input size. We're only using a few variables to keep track of the current node and the length.

This makes the two-pass approach quite efficient, especially in terms of space complexity. It's a great solution for this problem.

Common Mistakes and How to Avoid Them

When implementing this algorithm, there are a few common pitfalls to watch out for:

  1. Forgetting the Edge Case: Removing the Head Node

    • It's easy to overlook the case where you need to remove the head node. Remember to handle this separately by updating the head of the list directly.
    • How to Avoid: Always check if N is equal to the length of the list. If it is, return head.next.

  2. Incorrectly Calculating the Node to Remove

    • The formula (L - N) is crucial. A slight mistake here can lead to removing the wrong node.
    • How to Avoid: Double-check your calculations. Make sure you're traversing to the (L - N)th node from the beginning.

  3. Not Handling Invalid Input

    • If N is greater than the length of the list, it's an invalid input. Your code should handle this gracefully.
    • How to Avoid: Add a check to ensure N is within the valid range (1 to L). You can either return the original list or throw an error.

  4. Off-by-One Errors in Loops

    • It's common to make mistakes in the loop conditions, causing you to traverse one node too far or not far enough.
    • How to Avoid: Carefully review your loop conditions. Use a debugger or console.log statements to track the values of your variables and ensure you're iterating the correct number of times.

By being aware of these common mistakes, you can write more robust and error-free code.

Alternative Approaches

While the two-pass approach is a solid solution, there's another popular technique called the one-pass approach using two pointers. This approach is a bit more complex to grasp initially, but it achieves the same result in a single pass, potentially making it slightly more efficient in practice.

The One-Pass Approach

The one-pass approach uses two pointers, often called fast and slow. The idea is to move the fast pointer N nodes ahead of the slow pointer. Then, we move both pointers forward at the same pace. When the fast pointer reaches the end of the list, the slow pointer will be pointing to the node before the one we want to remove.

This approach eliminates the need to calculate the length of the list separately, which is why it can be done in one pass. However, it requires careful handling of the pointers and edge cases.

I might cover the one-pass approach in a future article, so stay tuned!

Conclusion

So, there you have it! We've successfully implemented the two-pass approach to remove the Nth node from the end of a linked list in JavaScript. We covered the problem, the algorithm, the code, and even some common mistakes to avoid. Remember, understanding data structures and algorithms is key to becoming a better developer. Keep practicing, and you'll master these concepts in no time! If you guys have any questions or want to discuss further, feel free to drop a comment below. Happy coding!