Here is solutions for Remove N-th Node From End of Linked List.

1. Understand the problem

• Given the head of a singly linked list and an integer n, remove the n-th node from the end of the list and return the head of the modified list.

2. Clarify constraints (ask 4–5 questions including edge cases)

1. What if the list is empty?

• If head is None, just return None.

1. What if n is larger than the length of the list?

• Typically constraints guarantee 1 ≤ n ≤ length. If not, add handling.

1. What if removing the first node (i.e., n == length)?

• You must return head.next.

1. Can the list have only 1 node?

• Yes → if n = 1, return None.

1. Are there negative values for n?

• No. n ≥ 1 by constraints.

3. Explore examples

4. Brainstorm 2-3 solutions

4.1. Solution 1: Naive Solution - Two Pass - Time O(N), Space: O(1).

• Find length L.

• Find node at position L - n.

• Remove next node.

• Time: O(L).

• Space: O(1)

4.2. Solution 2: Optimal – Fast & slow pointers - One pass - Gap Fast and Flow is N nodes, fast reach the end, slow in the N-th node from end - Time O(N), Space O(1)

• Idea: Keep fast above slow N nodes => Keep the gap is N.

• When fast reach to the end, slow is the nth node before end.

• Time: O(L).

• Space: O(1).

5. Implement solutions

5.1. Naive solution - One Pass - Time O(N), Space: O(N).

• Idea: Address store index and access arr[index] = address of the node, clean the node at index len(nodes) - n.

# 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]:
        nodes = []
        cur = head
        while cur:
            nodes.append(cur)
            cur = cur.next

        removeIndex = len(nodes) - n
        if removeIndex == 0:
            return head.next

        nodes[removeIndex - 1].next = nodes[removeIndex].next
        return head

• Time: O(N).

• Space: O(N).

5.2. Iteration (Two Pass) - Time O(N), Space: O(1).

• Idea: move pointer but do not use array to store.

# 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]:
        N = 0
        cur = head
        while cur:
            N += 1
            cur = cur.next

        removeIndex = N - n
        if removeIndex == 0:
            return head.next

        cur = head
        for i in range(N - 1):
            if (i + 1) == removeIndex:
                cur.next = cur.next.next
                break
            cur = cur.next
        return head

• Time: O(N).

• Space: O(1).

5.3. Recursion - Time O(N), Space: O(N).

• Idea: Move the pointer address to the end, decrase N when reach the end, if the n[0] = 0, remove the current pointer by point it to head.next (remove this node) => Otherwise keep the head address.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def rec(self, head, n):
        if not head:
            return None

        head.next = self.rec(head.next, n)
        n[0] -= 1
        if n[0] == 0:
            return head.next
        return head

    def removeNthFromEnd(self, head, n):
        return self.rec(head, [n])

• Time: O(N).

• Space: O(N).

5.4. Fast & slow pointers - One Pass - Time O(N), Space O(1)

• Idea: Keep fast above slow N nodes => Keep the gap is N. When fast reach to the end, slow is the nth node before end.

# 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(0, head)
        left = dummy
        right = head

        while n > 0:
            right = right.next
            n -= 1

        while right:
            left = left.next
            right = right.next

        left.next = left.next.next
        return dummy.next

• Time: O(N).

• Space: O(1).

6. Dry run examples

Example: list = [1 → 2 → 3 → 4 → 5], n = 2