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

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

• 难度: medium
• 原始链接: https://leetcode.cn/problems/insert-greatest-common-divisors-in-linked-list
• 标签: 辗转相除法

解法一: 辗转相除法

go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func insertGreatestCommonDivisors(head *ListNode) *ListNode {
    first := head
    second := head.Next
    for second != nil {
        first.Next = &ListNode{
            Val: gcd(first.Val, second.Val),
            Next: second,
        }
        first, second = second, second.Next
    }
    return head
}

func gcd(num1, num2 int) int {
    for num2 != 0 {
        num1, num2 = num2, num1 % num2
    }
    return num1
}