python|LeetCode 删除链表的倒数第 N 个节点 python|leetcode

删除链表的倒数第 N 个节点题目来源：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list
题目
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：
给定的 n 保证是有效的。
【python|LeetCode 删除链表的倒数第 N 个节点】进阶：
你能尝试使用一趟扫描实现吗？
解题思路

思路：链表+指针；
尝试使用一次扫描实现；
首先定义定义一个哑节点 dummy，哑节点下一个节点指向 head；
定义左右两个指针 left，right 指向 dummy；
先将右指针往前移动 n 步，然后两个指针同时移动，因为现在两个指针相隔 n 个节点，当右指针指向 null 时，左指针指向的节点就是要删除的节点。
时间复杂度：$O(L)$，$L$ 为列表的长度。

图解

文章图片

代码实现

# Definition for singly-linked list. # class ListNode: #def __init__(self, x): #self.val = x #self.next = Noneclass Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: # 定义一个哑节点，下一个节点指向 head dummy = ListNode(0) dummy.next = head # 定义左右两个指针指向哑节点 left = right = dummy # 右指针先往前移动 n 步 while n: right = right.next n -= 1 # 左右指针同时移动 # 现在左右指针相隔 n 步 # 当右指针 right 指向 null 时，left 指针指向的就是要删除的节点 # 所以当 right.next == null 时，停止移动，令 left.next = left.next.next while right.next: right = right.next left = left.next # 删除节点 left.next = left.next.next return dummy.next

实现结果