Day 21：2807. 在链表中插入最大公约数

Leetcode 2807. 在链表中插入最大公约数

给你一个链表的头 head ，每个结点包含一个整数值。
在相邻结点之间，请你插入一个新的结点，结点值为这两个相邻结点值的 最大公约数 。
请你返回插入之后的链表。
两个数的 最大公约数 是可以被两个数字整除的最大正整数。

重点是最大公约数的计算方式。

public int greatestDivisor(int a, int b) {
    while (a % b != 0) {
        int c = a % b;
        a = b;
        b = c;
    }
    return b;
}

还有就是要记住节点之间的连接。

完整代码

/**
 * 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) {
        ListNode pre = head;
        ListNode t = pre.next;
        while (t != null) {
            ListNode insert = new ListNode(greatestDivisor(pre.val, t.val), t);
            pre.next = insert;
            pre = t;
            t = t.next;
        }
        return head;
    }

    public int greatestDivisor(int a, int b) {
        while (a % b != 0) {
            int c = a % b;
            a = b;
            b = c;
        }
        return b;
    }
}