LeetCode 题解工作台
反转偶数长度组的节点
给你一个链表的头节点 head 。 链表中的节点 按顺序 划分成若干 非空 组，这些非空组的长度构成一个自然数序列（ 1, 2, 3, 4, ... ）。一个组的 长度 就是组中分配到的节点数目。换句话说： 节点 1 分配给第一组 节点 2 和 3 分配给第二组 节点 4 、 5 和 6 分配给第三…
1
题型
3
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
class Solution: def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你一个链表的头节点 head 。
链表中的节点 按顺序 划分成若干 非空 组，这些非空组的长度构成一个自然数序列（1, 2, 3, 4, ...）。一个组的 长度 就是组中分配到的节点数目。换句话说：
- 节点
1分配给第一组 - 节点
2和3分配给第二组 - 节点
4、5和6分配给第三组，以此类推
注意，最后一组的长度可能小于或者等于 1 + 倒数第二组的长度 。
反转 每个 偶数 长度组中的节点，并返回修改后链表的头节点 head 。
示例 1：
输入：head = [5,2,6,3,9,1,7,3,8,4] 输出：[5,6,2,3,9,1,4,8,3,7] 解释： - 第一组长度为 1 ，奇数，没有发生反转。 - 第二组长度为 2 ，偶数，节点反转。 - 第三组长度为 3 ，奇数，没有发生反转。 - 最后一组长度为 4 ，偶数，节点反转。
示例 2：
输入：head = [1,1,0,6] 输出：[1,0,1,6] 解释： - 第一组长度为 1 ，没有发生反转。 - 第二组长度为 2 ，节点反转。 - 最后一组长度为 1 ，没有发生反转。
示例 3：
输入：head = [2,1] 输出：[2,1] 解释： - 第一组长度为 1 ，没有发生反转。 - 最后一组长度为 1 ，没有发生反转。
提示：
- 链表中节点数目范围是
[1, 105] 0 <= Node.val <= 105
解题思路
方法一
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
def reverse(head, l):
prev, cur, tail = None, head, head
i = 0
while cur and i < l:
t = cur.next
cur.next = prev
prev = cur
cur = t
i += 1
tail.next = cur
return prev
n = 0
t = head
while t:
t = t.next
n += 1
dummy = ListNode(0, head)
prev = dummy
l = 1
while (1 + l) * l // 2 <= n and prev:
if l % 2 == 0:
prev.next = reverse(prev.next, l)
i = 0
while i < l and prev:
prev = prev.next
i += 1
l += 1
left = n - l * (l - 1) // 2
if left > 0 and left % 2 == 0:
prev.next = reverse(prev.next, left)
return dummy.next
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate should understand how to manipulate pointers in a linked list.
- question_mark
Look for a clear separation between how even and odd-length groups are handled.
- question_mark
The ability to explain why the last group may not always fit the typical pattern is important.
常见陷阱
外企场景- error
Failing to handle the last group when its size is smaller than expected.
- error
Reversing odd-length groups or failing to reverse even-length groups correctly.
- error
Not adjusting pointers properly during reversal can lead to broken lists.
进阶变体
外企场景- arrow_right_alt
What if the group lengths were randomly shuffled instead of sequential?
- arrow_right_alt
How would this problem change if each group could have its own predefined length?
- arrow_right_alt
How would you handle a situation where you need to reverse nodes in both even and odd-length groups alternatively?