LeetCode 题解工作台
在链表中插入最大公约数
给你一个链表的头 head ，每个结点包含一个整数值。 在相邻结点之间，请你插入一个新的结点，结点值为这两个相邻结点值的 最大公约数 。 请你返回插入之后的链表。 两个数的 最大公约数 是可以被两个数字整除的最大正整数。 示例 1： 输入： head = [18,6,10,3] 输出： [18,6,…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 链表指针操作
答案摘要
我们用两个指针 和 分别指向当前遍历到的结点和下一个结点，那么我们只需要在 和 之间插入一个新的结点即可。因此，每次计算出 和 的最大公约数 ，然后在 和 之间插入一个值为 的新结点，然后更新 $pre = cur$，并且 $cur = cur.next$，继续遍历链表，直到 为空。 时间复杂度 $O(n \times \log M)$，其中 是链表的长度，而 是链表中结点…
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 链表指针操作 题型思路
题目描述
给你一个链表的头 head ，每个结点包含一个整数值。
在相邻结点之间，请你插入一个新的结点，结点值为这两个相邻结点值的 最大公约数 。
请你返回插入之后的链表。
两个数的 最大公约数 是可以被两个数字整除的最大正整数。
示例 1：
输入：head = [18,6,10,3] 输出：[18,6,6,2,10,1,3] 解释：第一幅图是一开始的链表，第二幅图是插入新结点后的图（蓝色结点为新插入结点）。 - 18 和 6 的最大公约数为 6 ，插入第一和第二个结点之间。 - 6 和 10 的最大公约数为 2 ，插入第二和第三个结点之间。 - 10 和 3 的最大公约数为 1 ，插入第三和第四个结点之间。 所有相邻结点之间都插入完毕，返回链表。
示例 2：
输入：head = [7] 输出：[7] 解释：第一幅图是一开始的链表，第二幅图是插入新结点后的图（蓝色结点为新插入结点）。 没有相邻结点，所以返回初始链表。
提示：
- 链表中结点数目在
[1, 5000]之间。 1 <= Node.val <= 1000
解题思路
方法一：模拟
我们用两个指针 和 分别指向当前遍历到的结点和下一个结点，那么我们只需要在 和 之间插入一个新的结点即可。因此，每次计算出 和 的最大公约数 ，然后在 和 之间插入一个值为 的新结点，然后更新 ，并且 ，继续遍历链表，直到 为空。
时间复杂度 ，其中 是链表的长度，而 是链表中结点的最大值。忽略结果链表的空间消耗，空间复杂度 。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def insertGreatestCommonDivisors(
self, head: Optional[ListNode]
) -> Optional[ListNode]:
pre, cur = head, head.next
while cur:
x = gcd(pre.val, cur.val)
pre.next = ListNode(x, cur)
pre, cur = cur, cur.next
return head
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(n \cdot \log(\min(a,b))) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Check if the candidate handles linked list pointer manipulation correctly.
- question_mark
Look for understanding of efficient node insertion without unnecessary shifts.
- question_mark
Test whether the candidate anticipates and handles edge cases like single-node lists.
常见陷阱
外企场景- error
Failing to efficiently insert nodes, resulting in higher time complexity.
- error
Overlooking edge cases, such as when the list has only one node.
- error
Misunderstanding the GCD calculation, especially with large node values.
进阶变体
外企场景- arrow_right_alt
What if the problem requires you to insert the sum or product of adjacent nodes instead of the GCD?
- arrow_right_alt
Modify the problem to handle sorted linked lists or to add other number-theoretic operations.
- arrow_right_alt
Adjust the problem to use a doubly linked list instead of a singly linked list.