Remove Nth Node from End of List in DSA Javascript - Build from Scratch

Remove Nth Node from End of List

📖 Scenario: You are working on a music playlist app. The playlist is a linked list where each node holds a song title. Sometimes, users want to remove a song counting from the end of the playlist. Your task is to remove the Nth song from the end of the playlist.

🎯 Goal: Build a program that creates a linked list of songs, sets the position n from the end, removes the Nth song from the end, and prints the updated playlist.

📋 What You'll Learn

Create a linked list with exactly these songs in order: 'Song1', 'Song2', 'Song3', 'Song4', 'Song5'

Create a variable n with the value 2

Write a function removeNthFromEnd that removes the Nth node from the end of the linked list

Print the updated linked list after removal in the format: Song1 -> Song2 -> Song3 -> Song5 -> null

💡 Why This Matters

🌍 Real World

Removing the Nth node from the end of a linked list is useful in apps like music playlists, task managers, or message queues where you want to delete items counting from the end.

💼 Career

Understanding linked list manipulation and two-pointer techniques is important for software engineering interviews and working with data structures in real-world applications.

1

Create the linked list of songs

Create a linked list with nodes named head and each node having val and next. The list must have these songs in order: 'Song1', 'Song2', 'Song3', 'Song4', 'Song5'.

DSA Javascript

// Create linked list nodes for songs Song1 to Song5
// Your code here

Hint

Use a constructor function ListNode to create nodes. Link them by setting the next property.

2

Set the position n from the end

Create a variable called n and set it to 2.

DSA Javascript

function ListNode(val, next = null) {
  this.val = val;
  this.next = next;
}

const head = new ListNode('Song1',
  new ListNode('Song2',
    new ListNode('Song3',
      new ListNode('Song4',
        new ListNode('Song5')))));

// Create variable n and set it to 2
// Your code here

Hint

Just create a constant n and assign it the value 2.

3

Write the function to remove the Nth node from end

Write a function called removeNthFromEnd that takes head and n as parameters and removes the Nth node from the end of the linked list. Use two pointers named fast and slow to find the node to remove.

DSA Javascript

function ListNode(val, next = null) {
  this.val = val;
  this.next = next;
}

const head = new ListNode('Song1',
  new ListNode('Song2',
    new ListNode('Song3',
      new ListNode('Song4',
        new ListNode('Song5')))));

const n = 2;

// Your code here to write removeNthFromEnd function

Hint

Use a dummy node before head. Move fast pointer n+1 steps ahead. Then move fast and slow together until fast reaches the end. Remove the node after slow.

4

Print the updated playlist

Call removeNthFromEnd(head, n) and store the result in updatedHead. Then print the linked list starting from updatedHead in the format: Song1 -> Song2 -> Song3 -> Song5 -> null.

DSA Javascript

function ListNode(val, next = null) {
  this.val = val;
  this.next = next;
}

const head = new ListNode('Song1',
  new ListNode('Song2',
    new ListNode('Song3',
      new ListNode('Song4',
        new ListNode('Song5')))));

const n = 2;

function removeNthFromEnd(head, n) {
  const dummy = new ListNode(0, head);
  let fast = dummy;
  let slow = dummy;

  for (let i = 0; i <= n; i++) {
    fast = fast.next;
  }

  while (fast !== null) {
    fast = fast.next;
    slow = slow.next;
  }

  slow.next = slow.next.next;
  return dummy.next;
}

// Your code here to call function and print list

Hint

Call the function and then loop through the list to build a string showing each song followed by '->'. End with 'null'. Print the string.

Practice

1. What does the problem Remove Nth Node from End of List ask you to do?

easy

A. Delete the node that is the nth from the end in a linked list

B. Add a new node at the nth position from the start

C. Reverse the linked list up to the nth node

D. Find the value of the nth node from the start

Solution

1. Step 1: Understand the problem statement

   The problem asks to remove a node counting from the end of a linked list, not from the start.

2. Step 2: Identify the correct action

   Removing the nth node from the end means deleting that specific node and linking its previous node to the next node.

3. Final Answer:

   Delete the node that is the nth from the end in a linked list -> Option A

4. Quick Check:

   Remove nth from end = Delete nth from end [OK]

Hint: Count nodes from end, not start, to remove correct node [OK]

Common Mistakes:

• Confusing nth from end with nth from start
• Trying to reverse the list instead of removing
• Removing the wrong node index

2. Which of the following is the correct way to declare a function in JavaScript to remove the nth node from the end of a singly linked list?

easy

A. function removeNthFromEnd(head, n) { /* code */ }

B. removeNthFromEnd = (head, n) => { /* code */ }

C. All of the above

D. const removeNthFromEnd = function(head, n) { /* code */ }

Solution

1. Step 1: Review JavaScript function declaration styles

   JavaScript supports function declarations, function expressions, and arrow functions.

2. Step 2: Check each option

   function removeNthFromEnd(head, n) { /* code */ } is a function declaration, B is an arrow function, C is a function expression. All are valid ways to declare functions.

3. Final Answer:

   All of the above -> Option C

4. Quick Check:

   All function styles valid in JS [OK]

Hint: JS allows multiple function declaration styles [OK]

Common Mistakes:

• Thinking only one function syntax is valid
• Confusing arrow functions with older syntax
• Missing const or function keyword

3. What will be the output linked list after running this code snippet?

class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

function removeNthFromEnd(head, n) {
  let dummy = new ListNode(0, head);
  let first = dummy;
  let second = dummy;
  for (let i = 0; i <= n; i++) {
    first = first.next;
  }
  while (first !== null) {
    first = first.next;
    second = second.next;
  }
  second.next = second.next.next;
  return dummy.next;
}

// List: 1 -> 2 -> 3 -> 4 -> 5 -> null
let head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
let newHead = removeNthFromEnd(head, 2);

// Print list
let result = [];
while (newHead) {
  result.push(newHead.val);
  newHead = newHead.next;
}
console.log(result);

medium

A. [1, 2, 3, 4]

B. [1, 2, 4, 5]

C. [2, 3, 4, 5]

D. [1, 2, 3, 5]

Solution

1. Step 1: Understand the code logic

   The code uses two pointers with a dummy node to remove the nth node from the end. Here, n=2 means remove the 2nd last node (value 4).

2. Step 2: Trace the linked list after removal

   Original list: 1 -> 2 -> 3 -> 4 -> 5. Removing node with value 4 results in 1 -> 2 -> 3 -> 5.

3. Final Answer:

   [1, 2, 3, 5] -> Option D

4. Quick Check:

   Remove 2nd last node = remove 4 [OK]

Hint: Use two pointers spaced n apart to find node to remove [OK]

Common Mistakes:

• Removing the wrong node counting from start
• Not using dummy node causing errors on head removal
• Off-by-one error in loop for pointer movement

4. Identify the bug in this code snippet for removing the nth node from the end of a linked list:

function removeNthFromEnd(head, n) {
  let dummy = new ListNode(0, head);
  let first = dummy;
  let second = dummy;
  for (let i = 0; i < n; i++) {
    first = first.next;
  }
  while (first.next !== null) {
    first = first.next;
    second = second.next;
  }
  second.next = second.next.next;
  return dummy.next;
}

medium

A. The while loop condition should be first !== null instead of first.next !== null

B. The for loop should run from i = 0 to i <= n to move first pointer correctly

C. The dummy node is not needed and causes errors

D. second.next = second.next.next should be second.next.next = second.next

Solution

1. Step 1: Analyze the for loop pointer movement

   The for loop moves the first pointer n times, which is correct to create a gap of n nodes between first and second pointers.

2. Step 2: Understand the while loop condition

   The while loop condition should be first !== null to ensure the first pointer reaches the end, allowing the second pointer to point to the node before the target.

3. Final Answer:

   The while loop condition should be first !== null instead of first.next !== null -> Option A

4. Quick Check:

   Use while (first !== null) to correctly position second pointer [OK]

Hint: Use while (first !== null) to move pointers correctly [OK]

Common Mistakes:

• Moving first pointer only n times instead of n+1
• Incorrect while loop condition causing null errors
• Removing dummy node mistakenly

5. Given a linked list 1 -> 2 -> 3 -> 4 -> 5 -> null, what will be the resulting list after removing the 5th node from the end using the standard two-pointer approach?

hard

A. [1, 2, 3, 4]

B. [2, 3, 4, 5]

C. [1, 3, 4, 5]

D. [1, 2, 3, 5]

Solution

1. Step 1: Identify the node to remove

   Removing the 5th node from the end means removing the first node (value 1) because the list length is 5.

2. Step 2: Remove the head node and link next node as new head

   After removal, the list starts from node with value 2: 2 -> 3 -> 4 -> 5.

3. Final Answer:

   [2, 3, 4, 5] -> Option B

4. Quick Check:

   Remove 5th from end = remove head [OK]

Hint: Removing nth from end where n = list length removes head [OK]

Common Mistakes:

• Not handling removal of head node correctly
• Returning original list without removal
• Confusing nth from end with nth from start