How do I remove the nth node from the end of a linked list?

You can solve this by using the two-pointer technique, where one pointer is moved n steps ahead, and both pointers move together until the first pointer reaches the end.

What is the time complexity of removing the nth node from the end of the list?

The time complexity is O(sz), where sz is the number of nodes in the list, as we traverse the list at most twice.

Can I solve this problem using a single pass through the list?

Yes, using the two-pointer technique, you can solve the problem in a single pass, making it efficient.

What edge cases should I consider for this problem?

Edge cases include handling an empty list, a list with one element, and when n is equal to the length of the list.

How does the two-pointer approach work for this problem?

The two-pointer approach involves moving one pointer n steps ahead of the other. Then, both pointers move together until the first pointer reaches the end, at which point the second pointer will point to the node just before the one to be removed.

#19

Medium

auto_awesome链表指针操作

LeetCode 题解工作台

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

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。示例 1：输入： head = [1,2,3,4,5], n = 2 输出： [1,2,3,5] 示例 2：输入： head = [1], n = 1 输出： [] 示例 3：输入： head = [1,2], n = 1 输…

链表双指针

题目描述

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

示例 1：

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

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

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

lightbulb

解题思路

方法一：快慢指针

我们定义两个指针 fast 和 slow，初始时都指向链表的虚拟头结点 dummy。

接着 fast 指针先向前移动 $n$ 步，然后 fast 和 slow 指针同时向前移动，直到 fast 指针到达链表的末尾。此时 slow.next 指针指向的结点就是倒数第 n 个结点的前驱结点，将其删除即可。

时间复杂度 $O(n)$ ，其中 $n$ 为链表的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        fast = slow = dummy
        for _ in range(n):
            fast = fast.next
        while fast.next:
            slow, fast = slow.next, fast.next
        slow.next = slow.next.next
        return dummy.next

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for knowledge of linked-list pointer manipulation.
question_mark
Assess the candidate's understanding of two-pointer techniques.
question_mark
Evaluate their handling of edge cases, such as small lists or when n is at list boundaries.

warning

常见陷阱

外企场景

error
Not properly handling the edge case where the list has only one element or when n is equal to the list length.
error
Failing to correctly update the next pointer of the node before the one to be removed.
error
Misunderstanding the two-pointer technique and trying to manipulate the list in a less efficient way.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the list is cyclic? How would you handle that scenario?
arrow_right_alt
Remove the nth node from the beginning or middle of the list instead of the end.
arrow_right_alt
Modify the list such that it supports dynamic removals, rather than a fixed one-time operation.

help

常见问题

外企场景

继续练习

#61 旋转链表 #82 删除排序链表中的重复元素 II #86 分隔链表