Problem of The Day: Insert Greatest Common Divisors in Linked List
Problem Statement
Intuition
The problem involves modifying a linked list by inserting nodes between adjacent nodes based on the greatest common divisor (GCD) of their values. The first thought was to traverse the list while computing the GCD for each consecutive pair of nodes, inserting a new node between them with the GCD as its value.
Approach
- Traverse the linked list using a
while
loop. - For each pair of adjacent nodes, calculate the GCD of their values.
- Insert a new node between the two nodes, with the GCD as the node’s value.
- Continue the process until the end of the list is reached.
- Return the modified linked list.
Complexity
-
Time complexity: The time complexity is \(O(n)\), where \(n\) is the number of nodes in the linked list. This is because we traverse the list once, and each GCD calculation takes constant time.
-
Space complexity: The space complexity is \(O(1)\) since we are modifying the list in place and not using any additional data structures, aside from the new nodes being inserted.
Code
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def find_gcd(self, a, b):
while b:
a, b = b, a % b
return abs(a)
def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head.next is None:
return head
curr = head
while curr and curr.next:
next_node = curr.next
gcd = self.find_gcd(curr.val, next_node.val)
curr.next = ListNode(gcd, next_node)
curr = next_node
return head
Editorial
Approach: Simulation
class Solution:
def insertGreatestCommonDivisors(
self, head: Optional[ListNode]
) -> Optional[ListNode]:
# Helper method to calculate the greatest common divisor using the Euclidean algorithm
def _calculate_gcd(a, b):
while b != 0:
a, b = b, a % b
return a
# If the list contains only one node, return the head as no insertion is needed
if not head.next:
return head
# Initialize pointers to traverse the list
node1 = head
node2 = head.next
# Traverse the linked list
while node2:
gcd_value = _calculate_gcd(node1.val, node2.val)
gcd_node = ListNode(gcd_value)
# Insert the GCD node between node1 and node2
node1.next = gcd_node
gcd_node.next = node2
# Move to the next pair of nodes
node1 = node2
node2 = node2.next
return head