Question

LeetCode Link | 19. Remove Nth Node From End of List | Medium

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

Constraints

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

Examples

Example 1

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]

Solution Approach

Method: Two-pointers

Constrains

  • None

This method does not have any limitations. But keep in mind, this question assume n is never out of range or saying larger than the size of the linked list. Make sure you implement additional logic if no this assumption during interview.

Concept Explanation

This question is a classic application of the two-pointer technique. If you want to delete the nth node from the end, move the fast pointer n steps first, then move both fast and slow simultaneously until fast pointers to the end of the list. You can then delete the node that slow is pointing to.

Removing process

Detail Steps:

  1. Define the fast and slow pointers, initially set to the dummy head node.
  2. Fast pointer moves first, taking n + 1 steps. Why n + 1 steps? Because this allows slow to point to the node just before the one to be deleted when both pointers start moving simultaneously (this facilitates the deletion process).
  3. Move fast and slow together until fast points to the end of the list.
  4. Delete the node that follows the one slow is pointing to.
  5. Return header dummyNode.next

Code

  • Time complexity: O(n)
  • Space complexity: O(1)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */

function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
    let dummyNode: ListNode | null = new ListNode(0, head);
    let slowNode: ListNode = dummyNode;
    let fastNode: ListNode = dummyNode;

    while(n--) {
        fastNode = fastNode.next!;
    }
    while(fastNode.next) {
        fastNode = fastNode.next;
        slowNode = slowNode.next!;
    }
    slowNode.next = slowNode.next!.next;
    return dummyNode.next; 
}

Conclusion

Use this question to strengthen your mastery of the two-pointer technique. By ready to solve this question in condition that assume n is not in the size of linked list.