Design Gurus Logo
Solution: Remove Nth Node From End of List
Go Back

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

Using the input list = [1,2,3,4,5], n = 2:

  1. Initialize two pointers, first and second, at the head of the list.
  2. Move the first pointer 2 nodes ahead. Now, first points to "3" and second points to "1".
  3. Move both first and second pointers one step at a time. When first reaches "5", second will be at "3".
  4. The next node to second is "4", which is the node to be removed.
  5. Remove "4" by updating the next pointer of "3" to point to "5".
  6. The modified list is [1,2,3,5].

Code

Python3
Python3

Complexity Analysis

  • Time Complexity: O(L) - We traverse the list with two pointers. Here, L is the number of nodes in the list.
  • Space Complexity: O(1) - We only used constant extra space.