题目描述

[EN | CN]

给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。

示例:

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

说明:

给定的 n 保证是有效的。

进阶:

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

解法 1:双指针

用两个指针来处理就行,p2p1 提前走 n 步,然后同步前进,直到 p2 走到结尾,此时 p1 处就是要删除的结点。

有几个需要注意的地方:

  1. 指针 p2 需要提前走几步?什么时候停止?
  2. 指针 p1 应该指向要删除的结点吗?
  3. 如果删除的是头结点呢?
  4. 如果删除之后为空呢?

假设链表长度为 $n$,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(1)$,常数空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def removeNthFromEnd(self, head: ListNode, n: int) -> ListNode:
        pre = ListNode(-1)
        pre.next = head

        p1, p2 = pre, head
        for _ in range(n):
            p2 = p2.next
        while p2:
            p1, p2 = p1.next, p2.next
        p1.next = p1.next.next

        return pre.next
  • 执行用时:40 ms,在所有 Python3 提交中击败了 77.88% 的用户。
  • 内存消耗:13.7 MB,在所有 Python3 提交中击败了 5.41% 的用户。