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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Insert Greatest Common Divisors in Linked List

Difficulty: Medium

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.

Key Insights

  • The problem involves traversing a linked list and modifying it by inserting new nodes.
  • The greatest common divisor (GCD) needs to be calculated for every pair of adjacent nodes.
  • If the linked list has only one node, no insertion is needed.
  • Efficient calculation of GCD can be achieved using the Euclidean algorithm.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the linked list, since we need to traverse the list once.
Space Complexity: O(1), as we are modifying the linked list in place without using additional data structures.

Solution

The approach involves iterating through the linked list and for each pair of adjacent nodes, calculating their GCD. A new node with this GCD value is then created and inserted between the two nodes. This process continues until all pairs are processed.

  1. Start with the head of the linked list.
  2. While there are adjacent nodes:
    • Calculate the GCD of the current node and the next node.
    • Create a new node with this GCD value.
    • Adjust the pointers to insert the new node in the linked list.
  3. Continue until the end of the list.
  4. Return the modified head of the linked list.

Code Solutions

import math

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def insertGCD(head: ListNode) -> ListNode:
    current = head
    while current and current.next:
        # Calculate GCD of current node and next node
        gcd_value = math.gcd(current.val, current.next.val)
        new_node = ListNode(gcd_value)  # Create a new node with GCD value
        
        # Insert the new node
        new_node.next = current.next
        current.next = new_node
        
        # Move to the next pair
        current = new_node.next
    return head
← Back to All Questions