Loading... ![123.jpeg][1] ## 题目 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。 示例： 给定一个链表: 1->2->3->4->5, 和 n = 2. 当删除了倒数第二个节点后，链表变为 1->2->3->5. 说明： 给定的 n 保证是有效的。 进阶： 你能尝试使用一趟扫描实现吗？ 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 ---------- ## 两次遍历方法 删除倒数第几位数，我们的想法就是正着数，找到这个数在第几位数 所以， 我们使用一次遍历，来获取单链表的总长度 接着再用一次遍历，一边遍历，一边计数 当计数到达`总长度-倒数位数`的时候，就意味着我们找到这个数了 接着单链表的remove常规操作删除即可 ```python class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: cur = head length = 0 if not cur: return while cur: cur = cur.next length += 1 print(length) k, cur, pre = 0, head, head while cur: # length == n的情况，意味着删除第一位元素 # 此时，第一位元素是没有pre的 if length == n: head = cur.next return head elif k == length-n: pre.next = cur.next return head pre = cur cur = cur.next k += 1 ``` ## 快慢指针 快慢指针可以达到一次遍历就可以出结果，来看看实现过程吧 我们定义两个模拟指针`slow`和`fast` 数字既然在倒数第几位，那么我们可以先让`fast`指针走`n`位 之后，再同`slow`指针一起前进 当`fast`指针走到链表尾部的时候，停止 这个时候`slow`指针所指的位置，刚好就是要删除的元素 为了方便删除，我们可以将循环结束条件设置为`fast.next == None`即fast所指的下一位如果是None就结束 ```Python class Solution: def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode: slow=fast=head for i in range(n): if fast.next: fast = fast.next else: return head.next while fast.next: fast = fast.next slow = slow.next slow.next = slow.next.next return head ``` [1]: /usr/uploads/2020/03/311202236.jpeg Last modification：March 23rd, 2020 at 03:38 pm © 允许规范转载