在链表中插入最大公约数
难度:
标签:
题目描述
Given the head of a linked list head, in which each node contains an integer value.
Between every pair of adjacent nodes, insert a new node with a value equal to the greatest common divisor of them.
Return the linked list after insertion.
The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.
Example 1:
Input: head = [18,6,10,3] Output: [18,6,6,2,10,1,3] Explanation: The 1st diagram denotes the initial linked list and the 2nd diagram denotes the linked list after inserting the new nodes (nodes in blue are the inserted nodes). - We insert the greatest common divisor of 18 and 6 = 6 between the 1st and the 2nd nodes. - We insert the greatest common divisor of 6 and 10 = 2 between the 2nd and the 3rd nodes. - We insert the greatest common divisor of 10 and 3 = 1 between the 3rd and the 4th nodes. There are no more adjacent nodes, so we return the linked list.
Example 2:
Input: head = [7] Output: [7] Explanation: The 1st diagram denotes the initial linked list and the 2nd diagram denotes the linked list after inserting the new nodes. There are no pairs of adjacent nodes, so we return the initial linked list.
Constraints:
- The number of nodes in the list is in the range
[1, 5000]. 1 <= Node.val <= 1000
代码结果
运行时间: 40 ms, 内存: 19.3 MB
/*
* 思路：
* 1. 使用Stream生成链表的节点值列表。
* 2. 计算每两个相邻元素的GCD并将其插入到新列表中。
* 3. 创建新的链表节点，重构链表。
*/
import java.util.*;
import java.util.stream.*;
class ListNode {
int val;
ListNode next;
ListNode(int val) { this.val = val; }
}
public class Solution {
public ListNode insertGreatestCommonDivisors(ListNode head) {
if (head == null || head.next == null) return head;
List<Integer> values = new ArrayList<>();
for (ListNode curr = head; curr != null; curr = curr.next) {
values.add(curr.val);
}
List<Integer> result = IntStream.range(0, values.size() - 1)
.flatMap(i -> IntStream.of(values.get(i), gcd(values.get(i), values.get(i + 1))))
.boxed()
.collect(Collectors.toList());
result.add(values.get(values.size() - 1));
ListNode newHead = new ListNode(result.get(0));
ListNode current = newHead;
for (int i = 1; i < result.size(); i++) {
current.next = new ListNode(result.get(i));
current = current.next;
}
return newHead;
}
private int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
}
解释
方法:
此题解的思路是遍历给定的链表，并在每两个相邻结点之间插入一个新结点。新结点的值是这两个相邻结点的最大公约数（GCD）。为了实现这一点，算法使用Python标凑库中的math.gcd函数来计算两个数的最大公约数。遍历过程中，算法不断更新当前节点，将其指向未处理的下一个节点，直到所有相邻节点都处理完毕。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在处理链表时，如何确保在插入新节点后，原有节点的连接不会丢失或产生环状结构？
▷🦆
在`ListNode`类中，是否需要考虑异常处理，比如链表只有一个节点或链表为空的情况？
▷🦆
在插入新节点的过程中，如何处理链表的末尾节点，因为它没有后继节点与之计算GCD？
▷🦆
在计算GCD并创建新节点后，代码直接将新节点链接到后继节点，这样的实现方式是否会影响链表的遍历效率？
▷