2807. Insert Greatest Common Divisors in Linked List - Explanation

Problem Link

Description

You are 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 head of 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 = [12,3,4,6]

Output: [12,3,3,1,4,2,6]

Example 2:

Input: head = [2,1]

Output: [2,1,1]

Constraints:

• 1 <= The length of the list <= 5000.
• 1 <= Node.val <= 1000

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Simulation

Intuition

The problem asks us to insert a new node between every pair of adjacent nodes, where the new node's value is the GCD of its neighbors. We traverse the list and for each pair of consecutive nodes, compute their gcd and create a new node with that value.
The Euclidean algorithm efficiently computes the gcd: repeatedly replace the larger number with the remainder of dividing the two numbers until one becomes zero. The other number is the gcd.
Since we're inserting nodes as we traverse, we need to be careful to advance the pointer past the newly inserted node to avoid processing it again.

Algorithm

1. Start with cur pointing to the head of the list.
2. While cur.next exists:
   • Get the values of cur and cur.next as n1 and n2.
   • Compute their gcd using the Euclidean algorithm.
   • Create a new node with the gcd value.
   • Insert it between cur and cur.next by adjusting pointers.
   • Move cur to cur.next.next to skip over the newly inserted node.
3. Return the head of the modified list.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def gcd(a, b):
            while b > 0:
                a, b = b, a % b
            return a

        cur = head
        while cur.next:
            n1, n2 = cur.val, cur.next.val
            cur.next = ListNode(gcd(n1, n2), cur.next)
            cur = cur.next.next

        return head

Time & Space Complexity

• Time complexity: $O(n * \log (min(a, b)))$
• Space complexity:
  • $O(n)$ space for the gcd ListNodes.
  • $O(1)$ extra space.

Where $n$ is the length of the given list, and $a$ and $b$ are two numbers passed to the $gcd()$ function.