Problem Statement

Given a linked list, remove the last nth node from the end of the list and return the head of the modified list.

Example 1:

• Input: list = 1 -> 2 -> 3 -> 4 -> 5, n = 2
• Expected Output: 1 -> 2 -> 3 -> 5
• Justification: The 2nd node from the end is "4", so after removing it, the list becomes [1,2,3,5].

Example 2:

• Input: list = 10 -> 20 -> 30 -> 40, n = 4
• Expected Output: 20 -> 30 -> 40
• Justification: The 4th node from the end is "10", so after removing it, the list becomes [20,30,40].

Example 3:

• Input: list = 7 -> 14 -> 21 -> 28 -> 35, n = 3
• Expected Output: 7 -> 14 -> 28 -> 35
• Justification: The 3rd node from the end is "21", so after removing it, the list becomes [7,14,28,35].

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Solution

• Two-Pass Approach:

  • Begin by calculating the length of the linked list. This can be done by traversing the list from the head to the end.
  • Once the length is determined, calculate which node to remove by subtracting n from the length.
  • Traverse the list again and remove the node at the calculated position.

• One-Pass Approach using Two Pointers:

  • Use two pointers, first and second, and place them at the start of the list.
  • Move the first pointer n nodes ahead in the list.
  • Now, move both first and second pointers one step at a time until the first pointer reaches the end of the list. The second pointer will now be n nodes from the end.
  • Remove the node next to the second pointer.

• Advantage of One-Pass Approach:

  • The one-pass approach is more efficient as it traverses the list only once, whereas the two-pass approach requires two traversals.

• Edge Cases:

  • If n is equal to the length of the list, remove the head of the list.

Algorithm Walkthrough

Let's trace the first example, 1 -> 2 -> 3 -> 4 -> 5 with n = 2. Move through the steps one at a time:

Code