Leetcode Daily Question 10/09/2024 - 2807. Insert Greatest Common Divisors in Linked List

Problem Description:

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.

from typing import Optional
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]:
    dummy = ListNode(-1)
    dummy.next = head
    current = head
    while current and current.next:
      next_node = current.next
      GCD = math.gcd(current.val, next_node.val)
      gcd_node = ListNode(GCD)
      current.next = gcd_node
      gcd_node.next = next_node
      
      current = next_node
    
    return dummy.next

Explanation:

To solve this question we have to keep a clear track of how the nodes connect with each other.

We start by creating a dummy node, this points to our linked list and dummy.next acts as our output.

Then we traverse the linked list using the "current" variable which is set to equal the head of the linked list.

dummy = ListNode(-1)
dummy.next = head
current = head

During traversal, we first declare the next node variable which directs where current go.

We use next_node to calculate the gcd between current and current.next, and create a new node with this value.

Then we insert the new node by first telling current to go to this new node and pointing this new node back to the next node.

Finally, we push current to this next node.

while current and current.next:
  next_node = current.next
  GCD = math.gcd(current.val, next_node.val)
  
  gcd_node = ListNode(GCD)
  current.next = gcd_node
  gcd_node.next = next_node
  
  current = next_node

return dummy.next

The time complexity is O(n), where n is the number of nodes. This is because we need to traverse the linked list in its entirety to calculate and insert the new nodes.

The space complexity is O(n). We need to insert n - 1 new nodes into our linked list, so the space complexity is O(n + (n - 1)) = O(2n - 1) ~=~ O(n).

The full solution can be found near the top of the page.