1. 力扣2807：在链表中插入最大公约数
1.1 题目：
你一个链表的头 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
1.2 思路
这题的难点在于如果求两个相邻节点的最大公约数。如果两个值中的最大值可以与最小值整除，那么最小值就是最大公约数，否则我们用更相减损术（夸克搜的）。
1.3 题解：
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val = val; }* ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode insertGreatestCommonDivisors(ListNode head) {if(head == null || head.next == null){return head;}ListNode dummy = new ListNode(10086, head);ListNode cur = dummy;// 用来求最大公约数while(cur.next != null && cur.next.next != null){int a = cur.next.val;int b = cur.next.next.val;int max = Integer.max(a, b);int min = Integer.min(a, b);// 如果可以整除，最小值就是最大公约数if(max % min == 0){} else {// 更相减损术int sub = max - min;while(sub != min){max = Integer.max(sub, min);min = Integer.min(sub, min);sub = max - min;}}ListNode p = new ListNode(min, cur.next.next);cur.next.next = p;// 这里是p的原因在于：我们要处理的是cur的下一个节点和下下一个节点// 而p此时位于的节点刚好在要处理的两个节点前面cur = p;}return dummy.next;}
}