We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Insert Greatest Common Divisors in Linked List

Number: 2903

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Given the head of a linked list where each node contains an integer, between every pair of adjacent nodes, insert a new node with a value equal to the greatest common divisor (GCD) of the values in those two nodes. Return the modified linked list after the insertions.

Key Insights

  • Compute the GCD for each adjacent pair of nodes in one traversal.
  • Insert the new node immediately between the two nodes.
  • Since the linked list is traversed once, the solution is efficient.
  • Use the properties of the GCD function to streamline the process.

Space and Time Complexity

Time Complexity: O(n * log(max(a, b))) where n is the number of nodes and log(max(a, b)) is the complexity of each GCD computation. Space Complexity: O(1) (ignoring the output list space)

Solution

The solution involves iterating over the linked list exactly once. For each pair of adjacent nodes:

  1. Compute the GCD of the numbers stored in the current node and the next node.
  2. Create a new node with the computed GCD value.
  3. Insert the new node between the current node and the next node.
  4. Advance the pointer to the next original node (skipping over the inserted node). This algorithm uses constant extra space while modifying the linked list in place. The key challenge is correctly handling node pointers to avoid breaking the list structure during insertion.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

import math

def insertGreatestCommonDivisors(head: ListNode) -> ListNode:
    # Initialize the current pointer starting from the head.
    current = head
    # Iterate over the list until the end is reached.
    while current and current.next:
        # Store the next node to maintain reference.
        next_node = current.next
        # Calculate the GCD of the current node's value and the next node's value.
        gcd_value = math.gcd(current.val, next_node.val)
        # Create a new node with the GCD value.
        new_node = ListNode(gcd_value)
        # Insert the new node between current and next_node.
        current.next = new_node
        new_node.next = next_node
        # Move the pointer two nodes ahead (to the next original node).
        current = next_node
    # Return the modified list head.
    return head
← Back to All Questions