删除链表的倒数第 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 输出：[1]

双指针

思路

虚拟头节点：使用 dummy 节点简化边界处理，例如删除头节点时，无需特殊处理逻辑。
快慢指针移动：fast 指针先移动 n+1 步（多移动一步以便 slow 停留在目标节点的前一个节点）。之后同时移动 fast 和 slow，直到 fast 到达链表末尾。
删除目标节点：slow.next 指向 slow.next.next，跳过目标节点。
返回结果：返回 dummy.next，即删除目标节点后的链表头节点。

代码

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)  # 虚拟头节点
        fast = dummy
        slow = dummy

        # 让 fast 指针先移动 n+1 步
        for _ in range(n + 1):
            fast = fast.next

        # 同时移动 fast 和 slow，直到 fast 到达链表末尾
        while fast:
            fast = fast.next
            slow = slow.next

        # 删除 slow.next（即倒数第 n 个节点）
        slow.next = slow.next.next

        # 返回链表的头节点
        return dummy.next

Python

复杂度

时间复杂度：O(n): 遍历链表两次：一次移动 fast，一次移动 fast 和 slow。
空间复杂度：O(1): 使用常量空间。

注意事项

特殊情况处理：
- 如果需要删除的是头节点，应直接更新 head。
确保 slow 指针操作正确：
- 使用一个虚拟头节点 (dummy) 简化删除逻辑，避免处理边界条件（例如删除头节点）时的复杂性。
返回结果：
- 返回虚拟头节点的 next 作为链表的头节点，确保返回值始终正确。

两次遍历

思路

第一次遍历统计链表长度第二次遍历时删除倒数第n个节点

两两交换链表中的节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

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

示例 2：

输入：head = [] 输出：[]

示例 3：

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

方法

思路

虚拟头节点：使用 dummy 节点的 next 指向原链表的头节点，简化头节点的交换逻辑。
循环条件：检查 pre_node.next 和 pre_node.next.next 是否存在，确保当前的两个节点可以被交换。
节点交换：交换两个节点 node1 和 node2 的指针：
- pre_node.next 指向 node2。
- node1.next 指向 node2.next。
- node2.next 指向 node1。
更新指针：更新 pre_node 为 node1，继续下一对节点的交换。
返回结果：最后返回 dummy.next，即交换后的链表头节点。

代码

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 使用虚拟头节点
        dummy = ListNode(0, head)
        pre_node = dummy

        # 遍历链表，按两两节点交换
        while pre_node.next and pre_node.next.next:
            node1 = pre_node.next
            node2 = node1.next

            # 交换节点
            pre_node.next = node2
            node1.next = node2.next
            node2.next = node1

            # 更新前驱节点
            pre_node = node1

        # 返回交换后的链表头节点
        return dummy.next

Python

复杂度分析

时间复杂度：O(n)
- 遍历链表一次，每次交换两个节点。
空间复杂度：O(1)
- 使用常量级别的额外空间，无递归或额外数据结构。

K 个一组翻转链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

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

示例 2：

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

方法

思路

初始化：
- 创建一个虚拟头节点 dummy，将其 next 指向链表头部，方便统一处理头节点翻转的情况。
- 使用一个指针 pre_node，初始指向 dummy，作为每组翻转后链表的连接点。
分组检查：
- 使用 check_k 函数，检查从当前节点开始是否有足够的 kkk 个节点。如果不足 kkk，结束翻转操作。
分组翻转：
- 对当前组的 k个节点调用 reverse_listnode函数进行翻转：
  - 翻转函数返回翻转后的新头节点和新尾节点。
- 翻转完成后，更新当前组的前后链接：
  - 翻转后的新头节点通过 pre_node.next 连接到前一部分链表。
  - 翻转后的新尾节点通过 new_tail.next 连接到未翻转部分链表。
移动指针：
- 将 pre_node 更新为当前组的尾节点，继续处理下一组。
返回结果：
- 最后返回 dummy.next 作为新链表的头节点。

代码

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if not head or k == 1:
            return head

        # 翻转链表的前 k 个节点，返回翻转后的头和尾
        def reverse_listnode(head, k):
            prev = None
            curr = head
            for _ in range(k):
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node
            return prev, head  # 返回翻转后的头和尾

        # 检查是否有足够的 k 个节点
        def check_k(node, k):
            count = 0
            while node and count < k:
                node = node.next
                count += 1
            return count == k

        # 使用虚拟头节点
        dummy = ListNode(0, head)
        pre_node = dummy

        # 按 k 分组翻转链表
        while check_k(pre_node.next, k):
            group_head = pre_node.next  # 当前组的头节点
            group_tail = pre_node  # 当前组的尾节点将更新
            for _ in range(k):
                group_tail = group_tail.next

            next_group = group_tail.next  # 下一组的起点
            # 翻转当前组
            new_head, new_tail = reverse_listnode(group_head, k)
            # 更新前后链接
            pre_node.next = new_head
            new_tail.next = next_group

            # 更新 pre_node 为当前组的尾节点
            pre_node = new_tail

        return dummy.next

Python

复杂度

时间复杂度：O(n)
- 遍历链表一次，每次翻转 k 个节点，整体复杂度为线性。
空间复杂度：O(1)
- 除了少量变量外，没有额外的空间使用。

优化

优化思路

减少多余的长度检查：
- 在传统实现中，会多次检查是否有足够的 k 个节点（如 check_k 函数）。可以通过一次遍历统计链表长度来避免重复检查，从而优化性能。
减少递归使用（如果有）：
- 部分实现可能使用递归处理每组节点的翻转。虽然代码更简洁，但递归会导致额外的栈空间消耗，可能引发栈溢出。在实现中尽量使用迭代。
一次性计算尾部节点更新：
- 翻转组内的节点时，可以避免重复更新指针，将尾部节点的更新集中处理。
整合逻辑，减少冗余变量：
- 通过合并前后链接的处理逻辑和翻转逻辑，可以减少变量的使用和逻辑的复杂度。

代码

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        # 如果链表为空或 k 为 1（无需翻转），直接返回原链表
        if not head or k == 1:
            return head

        # 计算链表长度
        length = 0
        cur = head
        while cur:  # 遍历链表统计节点数
            length += 1
            cur = cur.next

        # 定义虚拟头节点 dum，便于处理头节点翻转的特殊情况
        # p0 指向每次翻转前的前驱节点，初始为虚拟头节点
        p0 = dum = ListNode(0, head)
        pre_node = None  # 翻转过程中的前驱节点
        cur_node = head  # 当前处理的节点（翻转组的起点）

        # 当剩余节点数 >= k 时，继续分组翻转
        while length >= k:
            # 翻转当前组的 k 个节点
            for i in range(k):
                next_node = cur_node.next  # 保存下一个节点，避免链表断裂
                cur_node.next = pre_node  # 翻转当前节点的指向
                pre_node = cur_node       # 更新前驱节点为当前节点
                cur_node = next_node      # 更新当前节点为下一个节点
            
            # 连接翻转后的链表部分
            next_node = p0.next  # 当前组翻转前的头节点（翻转后是尾节点）
            next_node.next = cur_node  # 当前组的尾节点连接到未翻转部分的头节点
            p0.next = pre_node         # 上一组的尾节点连接到当前组的头节点
            
            # 更新指针，为下一组翻转做准备
            p0 = next_node             # p0 更新为当前组的尾节点
            pre_node = None            # 重置前驱节点
            length -= k                # 减少剩余节点数

        # 返回虚拟头节点的 next，即翻转后的链表头节点
        return dum.next

Python

思路分析

首先是要遍历找到链表长度，之后根据长度每k长翻转一次链表，重点是翻转后的前后连接该如何修改。为了修改前后连接，可以使用一个变量 p0 作为本轮目标翻转链表的前一个Node，而因为当我们翻转完当前链表时我们的三个变量pre_node, cur_node 和next_node分别为当前链表翻转后的head节点，下一次要翻转的head节点。因此我们可以先使用p0.next作为翻转后的尾节点。此时当前翻转后的首尾节点，当前链表前节点与链表后节点就都知道了，现在就可以进行修改连接。

在使用p0.next作为翻转后的尾节点后我们可以将前节点p0与翻转后首节点pre_node连接，之后将翻转后尾节点与链表后节点cur_node 连接，这样就修改了当前链表的前后连接，最后可以将p0重新设置为下一个翻转链表的前节点，也就是现在的next_node

复杂度

时间复杂度：O(n)
- 统计链表长度：O(n)。
- 按组翻转：每个节点被访问一次，总复杂度为 O(n)。
空间复杂度：O(1)
- 只使用了常量级别的辅助变量，没有额外的数据结构。

方法二：递归

5betgame

iPhone Safari

2 周前
2026-3-22 5:08:29

Just started exploring 5betgame. Initial impression? Seems decent, solid, but not amazing. If you are bored you can always go there 5betgame.
okbajicasino

iPhone Safari

2 周前
2026-3-22 5:08:48

Okay, so OKBajiCasino… It’s all right! If you’re looking for a quick game of a casino then this is for you. okbajicasino
jw7login

iPhone Safari

2 周前
2026-3-22 5:09:07

Can’t say too much about JW7Login, but the login process is smooth. Sometimes that’s all you really need, right? A hassle-free experience. jw7login

一	二	三	四	五	六	日
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30

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

双指针

思路

代码

复杂度

注意事项

两次遍历

思路

两两交换链表中的节点

方法

思路

代码

复杂度分析

K 个一组翻转链表

方法

思路

代码

复杂度

优化

优化思路

代码

思路分析

复杂度

方法二：递归

评论

发送评论编辑评论

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

双指针

思路

代码

复杂度

注意事项

两次遍历

思路

两两交换链表中的节点

方法

思路

代码

复杂度分析

K 个一组翻转链表

方法

思路

代码

复杂度

优化

优化思路

代码

思路分析

复杂度

方法二：递归

评论

发送评论 编辑评论

推荐文章

发送评论编辑评论