python-leetcode-删除链表的倒数第-N-个结点
目录
python-leetcode-删除链表的倒数第 N 个结点
可以使用双指针方法来解决这个问题，这样可以在一次遍历内完成删除操作，从而达到 O(n) 的时间复杂度。以下是 Python 代码实现：
解题思路：
- 初始化快慢指针
：使用两个指针
fast和slow，都指向头结点。 - 快指针先走 n 步 ：这样当快指针到达链表末尾时，慢指针正好指向倒数第 n 个节点的前一个节点。
- 同时移动快慢指针 ：直到快指针到达链表的末尾。
- 删除目标节点
：调整前一个节点的
next指针。
Python 代码：
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
dummy = ListNode(0, head) # 添加哑节点，方便处理边界情况
fast = slow = dummy # 快慢指针初始化指向哑节点
# 让快指针先走 n+1 步，这样 slow 指向待删除节点的前一个节点
for _ in range(n + 1):
fast = fast.next
# 同时移动快慢指针，直到快指针到达链表尾部
while fast:
fast = fast.next
slow = slow.next
# 删除倒数第 n 个节点
slow.next = slow.next.next
return dummy.next # 返回真正的头节点复杂度分析
- 时间复杂度： O(n)，只遍历了一次链表。
- 空间复杂度： O(1)，只用了常数级额外空间。
示例
# 构造链表 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
# 删除倒数第 2 个节点
new_head = removeNthFromEnd(head, 2)
# 打印新链表
cur = new_head
while cur:
print(cur.val, end=" -> ")
cur = cur.next
# 输出：1 -> 2 -> 3 -> 5 ->这个方法使用了 哑节点（dummy node） ，有效地避免了删除头节点的特殊情况，使代码更加简洁稳健。