题目

题目地址：

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 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

思路

两趟变量

快慢指针(一个先走 n+1 步（有伪节点的情况下）,那么他们的间隔就是固定的)

递归

代码

测试用例

  • 边界条件

程序

快慢指针

时间复杂度：O(L)，该算法对含有 L 个结点的列表进行了一次遍历。因此时间复杂度为 O(L)。
空间复杂度：O(1)，我们只用了常量级的额外空间。

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  7. class Solution:
  8.     def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
  9.         dummy = ListNode(0)
  10.         dummy.next = head
  11.         slow, fast = dummy, dummy
  12.         for _ in range(n+1):
  13.             if fast:
  14.                 fast = fast.next
  15.         while fast:
  16.             slow = slow.next
  17.             fast = fast.next
  18.         slow.next = slow.next.next
  19.         return dummy.next

递归（不是很明白）

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, x):
  4. #         self.val = x
  5. #         self.next = None
  7. class Solution:
  8.     def __init__(self):
  9.         self.cur = 0
  11.     def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:        
  12.         if not head:
  13.             return None
  14.         head.next = self.removeNthFromEnd(head.next, n)
  15.         self.cur += 1
  16.         if n == self.cur:
  17.             return head.next
  18.         return head