#19

Medium

auto_awesomeLinked-list pointer manipulation

LeetCode Problem Workspace

Remove Nth Node From End of List

Remove the nth node from the end of a linked list using a two-pointer approach to solve efficiently.

Problem Statement

You are given the head of a singly linked list, and an integer n. Your task is to remove the nth node from the end of the list and return its head.

For example, given a list head = [1,2,3,4,5] and n = 2, after removing the second node from the end, the list should become [1,2,3,5].

Examples

Example 1

Input: head = [1,2,3,4,5], n = 2

Output: [1,2,3,5]

Example details omitted.

Example 2

Input: head = [1], n = 1

Output: []

Example details omitted.

Example 3

Input: head = [1,2], n = 1

Output: [1]

Example details omitted.

Constraints

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

Solution Approach

Two Pointer Approach

Start by placing two pointers on the head of the list. Move one pointer n steps forward. Then move both pointers one step at a time until the first pointer reaches the end. The second pointer will then be just before the node to be removed.

Edge Case Handling

Handle edge cases such as when the list contains only one element, or when n equals the size of the list. In these cases, you need to remove the first node or handle list emptying properly.

Update List Pointers

When the second pointer reaches the node just before the one to be removed, update its next pointer to skip the node. This efficiently removes the target node from the list.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity is O(sz) because we traverse the list at most twice, where sz is the number of nodes in the list. The space complexity is O(1) as we only use two pointers, irrespective of the list size.

What Interviewers Usually Probe

Look for knowledge of linked-list pointer manipulation.
Assess the candidate's understanding of two-pointer techniques.
Evaluate their handling of edge cases, such as small lists or when n is at list boundaries.

Common Pitfalls or Variants

Common pitfalls

Not properly handling the edge case where the list has only one element or when n is equal to the list length.
Failing to correctly update the next pointer of the node before the one to be removed.
Misunderstanding the two-pointer technique and trying to manipulate the list in a less efficient way.

Follow-up variants

What if the list is cyclic? How would you handle that scenario?
Remove the nth node from the beginning or middle of the list instead of the end.
Modify the list such that it supports dynamic removals, rather than a fixed one-time operation.

FAQ

How do I remove the nth node from the end of a linked list?

You can solve this by using the two-pointer technique, where one pointer is moved n steps ahead, and both pointers move together until the first pointer reaches the end.

What is the time complexity of removing the nth node from the end of the list?

The time complexity is O(sz), where sz is the number of nodes in the list, as we traverse the list at most twice.

Can I solve this problem using a single pass through the list?

Yes, using the two-pointer technique, you can solve the problem in a single pass, making it efficient.

What edge cases should I consider for this problem?

Edge cases include handling an empty list, a list with one element, and when n is equal to the length of the list.

How does the two-pointer approach work for this problem?

The two-pointer approach involves moving one pointer n steps ahead of the other. Then, both pointers move together until the first pointer reaches the end, at which point the second pointer will point to the node just before the one to be removed.

terminal

Solution

Solution 1: Fast and Slow Pointers

We define two pointers `fast` and `slow`, both initially pointing to the dummy head node of the linked list.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        fast = slow = dummy
        for _ in range(n):
            fast = fast.next
        while fast.next:
            slow, fast = slow.next, fast.next
        slow.next = slow.next.next
        return dummy.next

Continue Practicing

#61 rotate list #82 remove duplicates from sorted list ii #86 partition list