当前位置：首页 > article >正文

LeetCode练习-删除链表的第n个结节

article 2024/10/27 15:09:53

大家好，依旧是你们的萧萧啊。

今天我们来练习一个经典的链表问题：删除链表的第n个节点。在这篇文章中，我们将深入分析这个问题，并给出一个有效的解决方案。

问题描述

给定一个链表，要求删除链表的倒数第n个节点，并返回链表的头节点。我们需要考虑以下示例：

示例 1：
- 输入：head = [1, 2, 3, 4, 5], n = 2
- 输出：[1, 2, 3, 5]
示例 2：
- 输入：head = [1], n = 1
- 输出：[]
示例 3：
- 输入：head = [1, 2], n = 1
- 输出：[1]

解决方案

在解决这个问题时，我们可以使用双指针的方法，这是一种高效且简单的思路。以下是解决该问题的步骤：

创建一个虚拟头节点：这个节点指向链表的头部，方便处理边界情况（如删除头节点）。
移动指针：使用两个指针（first 和 second）。首先，移动 first 指针到链表的第n+1个节点。
同时移动两个指针：然后，同时移动 first 和 second，直到 first 到达链表的末尾。此时，second 指向要删除节点的前一个节点。
删除节点：修改指针，跳过要删除的节点。
返回新头节点：最后，返回虚拟头节点的下一个节点，即新的头节点。

代码实现

下面是上述思路的代码实现：

# 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
        first = dummy
        second = dummy
        
        # 移动 first 指针 n + 1 步
        for _ in range(n + 1):
            first = first.next
        
        # 同时移动 first 和 second 指针，直到 first 到达链表的末尾
        while first:
            first = first.next
            second = second.next
        
        # 删除倒数第 n 个节点
        second.next = second.next.next
        
        return dummy.next  # 返回新的头节点