2807. Insert Greatest Common Divisors in Linked List

T: O(n*log(min(a, b))
S: O(1)

/**
 * 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 dummy = head;
        ListNode prev = new ListNode(-1);
        prev.next = dummy;

        while (dummy != null) {
            if (prev.val != -1) {
                int gcd = gcd(prev.val, dummy.val);
                prev.next = new ListNode(gcd, dummy);
            }
            prev = dummy;
            dummy = dummy.next;
        }
        return head;
    }
    private int gcd(int a, int b) { 
        if (b == 0) {
            return a;
        }
        return gcd (b, a%b);
    }
}

/**
T: O(n*log(min(a, b))
S: O(1)
 */