LeetCode【0019】删除链表的倒数第N个结点

1 中文题目

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

示例：

链表如上：
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

输入：head = [1], n = 1
输出：[]

输入：head = [1,2], n = 1
输出：[1]

提示：

• 链表中结点的数目为 sz
• $1\le sz\le 30$
• $0\le Node.val\le 100$
• $1\le n\le sz$

---

2 求解方法：虚拟头节点和快慢指针

2.1 方法思路

方法核心

使用虚拟头节点统一操作逻辑，采用快慢指针确定删除位置，快指针先走n步，然后快慢指针同步移动，直到快指针到达末尾

实现步骤

• 创建虚拟头节点阶段：
  • 新建值为0的虚拟节点
  • 将虚拟节点指向原链表头部
• 初始化快慢指针阶段：
  • 快慢指针都指向虚拟头节点
  • 确保初始状态一致
• 快指针移动阶段：
  • 快指针向前移动n步
  • 建立n个节点的间隔
• 双指针同步移动阶段：
  • 快慢指针同时向前移动
  • 直到快指针到达链表末尾
• 删除目标节点阶段：
  • 慢指针此时位于待删除节点的前一个位置
  • 修改next指针完成删除操作

方法示例

输入：head = [1,2,3,4,5], n = 2
# 1. 初始状态：创建虚拟头节点，快慢指针都指向虚拟头节点
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
↑
fast
↑
slow
(dummy)

# 2. 快指针先移动n=2步
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
↑         ↑
slow      fast
(dummy)

# 3. 快慢指针同时移动，直到快指针的next为NULL
# 移动过程中的状态：
# 第一步：
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
     ↑         ↑
    slow      fast

# 第二步：
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
          ↑         ↑
         slow      fast

# 第三步：
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
               ↑         ↑
              slow      fast

# 4. 此时slow指向待删除节点(4)的前一个节点(3)
# 执行删除操作：slow.next = slow.next.next
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL
               ↑         ↑
              slow      fast
              
变为：
0 -> 1 -> 2 -> 3 -----→ 5 -> NULL
               ↑        ↑
              slow     fast

# 5. 最后返回dummy.next，即返回真实的头节点
1 -> 2 -> 3 -> 5 -> NULL

2.2 Python代码

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        # 创建虚拟头节点，统一处理逻辑，避免分类讨论
        dummy = ListNode(0)
        dummy.next = head
        
        # 初始化快慢指针，都指向虚拟头节点
        fast = slow = dummy
        
        # 第一步：快指针先走n步
        # 这样后面快指针到末尾时，慢指针正好在待删除节点的前一个位置
        for i in range(n):
            fast = fast.next
            
        # 第二步：快慢指针同时移动
        # fast.next 判断确保fast最后指向最后一个节点
        while fast.next:
            fast = fast.next
            slow = slow.next
            
        # 第三步：删除倒数第n个节点
        # slow指向待删除节点的前一个节点
        slow.next = slow.next.next
        
        # 返回真实头节点
        return dummy.next

2.3 复杂度分析

• 时间复杂度：$O(N)$，其中$N$为链表长度
  • 快指针先走$n$步：$O(n)$
  • 快慢指针同步走到末尾：$O(N-n)$
• 空间复杂度：$O(1)$
  • 只使用了虚拟头节点：$O(1)$
  • 快慢指针：$O(1)$

---

3 题目总结

题目难度：中等
数据结构：链表
应用算法：快慢双指针

原文地址：https://blog.csdn.net/qq_32882309/article/details/143725827

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！