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.

LeetCode Problem - 2807

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;        // Value stored in the node
 *     ListNode next;  // Reference to the next node in the list
 *     ListNode() {}   // Default constructor
 *     ListNode(int val) { this.val = val; }  // Constructor with value only
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }  // Constructor with value and next node
 * }
 */
class Solution {
    // Method to insert the greatest common divisor (GCD) between consecutive nodes in a linked list
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        // If the list is empty or has only one node, return the list as is
        if (head == null || head.next == null) return head;

        // Initialize pointers for traversing the original list and constructing the new list
        ListNode tempHead = head;
        ListNode answer = new ListNode(); // Dummy node to simplify list construction
        ListNode tempAns = answer; // Pointer to build the new list

        // Traverse through the linked list
        for (ListNode current = tempHead; current != null; current = current.next) {
            // Check if the current node has a next node
            if (current.next != null) {
                // Get the values of the current node and the next node
                int val1 = current.val;
                int val2 = current.next.val;
                // Calculate the GCD of the two values
                int gcd = gcd(val1, val2);

                // Insert the current value, GCD, and next value into the new list
                tempAns.next = new ListNode(val1); // Add current node's value
                tempAns.next.next = new ListNode(gcd); // Add GCD between current and next node
                tempAns.next.next.next = new ListNode(val2); // Add next node's value
                tempAns = tempAns.next.next; // Move the pointer to the last added node
            }
        }
        // Return the new list, skipping the dummy node
        return answer.next;
    }

    // Helper method to calculate the greatest common divisor (GCD) using Euclidean algorithm
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a; // Base case: if b is 0, GCD is a
        }
        return gcd(b, a % b); // Recursive case
    }
}