3.0019. 删除链表的倒数第 N 个结点

3.1 题目大意

描述：给定一个链表的头节点 head。

要求：删除链表的倒数第 n 个节点，并且返回链表的头节点。

说明：

  • 要求使用一次遍历实现。
  • **链表中结点的数目为 **sz。

示例：

img

1
2
3
4
5
6
 输入：head = [1,2,3,4,5], n = 2
 输出：[1,2,3,5]
 
 
 输入：head = [1], n = 1
 输出：[]

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 class Solution:
     def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
         slow, fast = head, head
         
         # fast 先走 n 步
         for _ in range(n):
             fast = fast.next
         
         # 如果 fast 走到 None，说明删除的是头节点
         if not fast:
             return head.next
         
         # 同步移动，直到 fast 到最后一个节点
         while fast.next:
             slow = slow.next
             fast = fast.next
         
         # 删除 slow.next 节点
         slow.next = slow.next.next
         return head
 

3.4.2 题目大意

描述：给定一个单链表的头节点 head。

要求：返回链表的中间节点。如果有两个中间节点，则返回第二个中间节点。

说明：

  • **给定链表的结点数介于 **1 和 100 之间。

示例：

1
2
3
4
5
6
7
8
9
10
 输入：[1,2,3,4,5]
 输出：此列表中的结点 3 (序列化形式：[3,4,5])
 解释：返回的结点值为 3 。
 注意，我们返回了一个 ListNode 类型的对象 ans，这样：
 ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
 
 
 输入：[1,2,3,4,5,6]
 输出：此列表中的结点 4 (序列化形式：[4,5,6])
 解释：由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。

题解：

1
2
3
4
5
6
7
8
 class Solution:
     def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
         slow, fast = head, head
         while fast and fast.next:
             slow = slow.next
             fast = fast.next.next
         return slow