[LeetCode] 2807. Insert Greatest Common Divisors in Linked List

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

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

思路

按照题意，在每两个相邻的 node 之间再插入一个新的 node。注意求最大公约数的做法，需要时常复习。

复杂度

时间O(n)
空间O(1)

代码

Java实现

/**
 * 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) {
        // corner case
        if (head == null || head.next == null) {
            return head;
        }

        // normal case
        ListNode cur = head;
        while (cur.next != null) {
            int first = cur.val;
            int second = cur.next.val;
            ListNode newNode = new ListNode(gcd(first, second));
            newNode.next = cur.next;
            cur.next = newNode;
            cur = cur.next.next;
        }
        return head;
    }

    private int gcd(int a, int b) {
        if (a == 0) {
            return b;
        }
        if (b == 0) {
            return a;
        }
        if (a == b) {
            return a;
        }
        if (a > b) {
            return gcd(a - b, b);
        }
        return gcd(b - a, a);
    }
}