LeetCode: 19 Remove Nth Node From End of linked list

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

Example:

Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
Explanation: The second node from the end is 4, so we remove it and link 3 to 5.

Example:

Input: head = [1], n = 1
Output: []
Explanation: The list is empty after removing the only node.

Example:

Input: head = [1,2], n = 1
Output: [1]
Explanation: The second node from the end is 2, so we remove it.

问题

给定一个链表的头节点，删除链表的倒数第 n 个节点，并返回其头节点。

解决方案 1

双指针法

Approach 1 / 方法 1

This solution uses the two-pointer technique, often called the "fast and slow pointer" method. The idea is to move one pointer (fast) n steps ahead, then move both pointers together until the fast pointer reaches the end of the list. At that point, the slow pointer will be just before the node to be removed.

该解决方案使用双指针技术，通常称为“快慢指针”法。其思想是将一个指针（fast）向前移动 n 步，然后同时移动两个指针，直到 fast 指针到达列表的末尾。此时，slow 指针将位于要删除的节点之前。

Implementation / 实现

python

# 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: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        fast = slow = dummy

        # Move fast pointer n+1 steps ahead
        for _ in range(n + 1):
            fast = fast.next

        # Move both pointers until fast reaches the end
        while fast:
            fast = fast.next
            slow = slow.next

        # Remove the nth node
        slow.next = slow.next.next

        return dummy.next

Explanation / 解释

1. Step 1: Initialize a Dummy Node / 步骤 1: 初始化一个哑节点

   • A dummy node is used to handle edge cases easily, such as removing the first node. This dummy node points to the head of the list.
   • 哑节点用于轻松处理边缘情况，例如删除第一个节点。这个哑节点指向链表的头节点。

2. Step 2: Move the Fast Pointer / 步骤 2: 移动快指针

   • Move the fast pointer n + 1 steps ahead. This ensures that the slow pointer is exactly one step before the node to be removed.
   • 将 fast 指针向前移动 n + 1 步。这确保 slow 指针恰好位于要删除的节点之前。

3. Step 3: Move Both Pointers / 步骤 3: 同时移动两个指针

   • Move both fast and slow pointers one step at a time until fast reaches the end of the list. At this point, slow will be right before the node that needs to be removed.
   • 同时移动 fast 和 slow 指针，一次移动一步，直到 fast 到达列表末尾。此时，slow 将恰好位于需要删除的节点之前。

4. Step 4: Remove the Nth Node / 步骤 4: 删除倒数第 n 个节点

   • The node to be removed is slow.next. We bypass this node by setting slow.next = slow.next.next.
   • 要删除的节点是 slow.next。通过设置 slow.next = slow.next.next 来跳过该节点。

5. Step 5: Return the New Head / 步骤 5: 返回新的头节点

   • Finally, return dummy.next, which points to the new head of the list.
   • 最后，返回 dummy.next，它指向链表的新头节点。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n), where n is the length of the list. We make a single pass through the list.
• Space Complexity / 空间复杂度: O(1), since we are using a constant amount of extra space.

Key Concept / 关键概念

• Two-Pointer Technique: This method efficiently removes the nth node from the end of a singly linked list in a single pass.
• 双指针技术: 该方法通过单次遍历高效地从单链表的末尾删除第 n 个节点。

解决方案 2

计算链表长度法

Approach 2 / 方法 2

This solution involves two passes through the list. First, we calculate the total length of the list. Then, we find the position to remove by calculating length - n and remove the node at that position.

该解决方案涉及两次遍历列表。首先，我们计算列表的总长度。然后，我们通过计算 length - n 找到要删除的位置，并删除该位置的节点。

Implementation / 实现

python

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        length = 0
        first = head

        # First pass to calculate the length of the list
        while first:
            length += 1
            first = first.next

        # Find the length - n node
        length -= n
        first = dummy
        while length > 0:
            length -= 1
            first = first.next

        # Remove the nth node
        first.next = first.next.next

        return dummy.next

Explanation / 解释

1. Step 1: Calculate the Length / 步骤 1: 计算链表长度

   • Traverse the list to find its length. The first pointer is used to traverse the list and count the nodes.
   • 遍历链表以找到其长度。使用 first 指针遍历链表并计数节点。

2. Step 2: Find the (Length – N)th Node / 步骤 2: 找到（长度 – n）位置的节点

   • Calculate the position of the node to remove by finding length - n. Start from the dummy node and move forward until reaching this position.
   • 通过找到 length - n 来计算要删除的节点位置。从哑节点开始，向前移动，直到到达此位置。

3. Step 3: Remove the Node / 步骤 3: 删除节点

   • Bypass the node at length - n by setting first.next = first.next.next.
   • 通过设置 first.next = first.next.next 来跳过 length - n 位置的节点。

4. Step 4: Return the New Head / 步骤 4: 返回新的头节点

   • Finally, return dummy.next, which points to the new head of the list.
   • 最后，返回 dummy.next，它指向链表的新头节点。

Complexity Analysis / 复杂度分析

• Time Complexity / 时间复杂度: O(n), where n is the length of the list. We make two passes through the list.
• Space Complexity / 空间复杂度: O(1), since we are using a constant amount of extra space.

Key Concept / 关键概念

• Two-Pass Approach: This method calculates the length first and then removes the nth node, which may be easier to understand but requires two passes.
• 双遍历法: 该方法先计算长度，然后删除倒数第 n 个节点，可能更容易理解，但需要两次遍历。

Comparison / 比较

1. Efficiency:

   • Approach 1 (Two-Pointer Method) is more efficient since it requires only one pass through the list.
   • Approach 2 (Length Calculation Method) requires two passes, which is less efficient but still acceptable for smaller lists.

2. Simplicity:

   • Approach 2 might be easier to understand conceptually since it directly calculates the length and then removes the node.

3. Use Case:

   • Approach 1 is preferred when performance is critical, especially for longer lists.
   • Approach 2 can be useful if the problem of counting the length is explicitly part of the challenge or if understanding the two-pointer technique is not crucial.

Summary / 总结

Both approaches solve the problem effectively, but the two-pointer technique is generally more efficient. It’s an excellent method to learn for various linked list problems where you need to find or remove elements based on their position from the end of the list.

Tips / 提示

• Two-Pointer Method is a powerful technique that often comes up in linked list problems, so it’s good to understand it well.
• Dummy Nodes can simplify edge cases like removing the first or last node in a list.

What does the main algorithm of this question aim to test? / 这个问题的主要算法旨在测试什么？

Understanding of linked list traversal techniques and the ability to handle edge cases when removing elements from a singly linked list.

5 more similar questions / 推荐5问题

1. LeetCode 206. Reverse Linked List
2. LeetCode 21. Merge Two Sorted Lists
3. LeetCode 234. Palindrome Linked List
4. LeetCode 141. Linked List Cycle
5. LeetCode 876. Middle of the Linked List

Recommended Resources:

Remove Nth Node from End of List – Oracle Interview Question – Leetcode 19 by NeetCode

LeetCode 19: Remove Nth Node From End of List | 2 Pointers, 1 Pass by Algo Engine