Sponsored
Sponsored
This approach involves iterating through the linked list while moving two pointers: a 'current' pointer to track the current node, and a 'next_node' pointer to track the next node. For each pair of adjacent nodes, compute their GCD and insert a new node with this GCD value between them.
Time Complexity: O(n), where n is the number of nodes, as we traverse once through the list and perform constant-time operations on each pair of nodes.
Space Complexity: O(1), since we only use a fixed amount of additional space.
1class ListNode:
2 def __init__(self, val=0, next=None):
3 self.val = val
4 self.next = next
5
6from math import gcd
7
8def insert_gcds(head: ListNode) -> ListNode:
9 if not head or not head.next:
10 return head
11
12 current = head
13 while current and current.next:
14 gcd_value = gcd(current.val, current.next.val)
15 new_node = ListNode(gcd_value)
16 new_node.next = current.next
17 current.next = new_node
18 current = new_node.next
19 return headThe Python code defines a ListNode class and uses Python's inbuilt 'gcd' function from the math module. It traverses the linked list with a pointer called 'current'. For each pair of adjacent nodes, it calculates the GCD and inserts a new node containing this GCD between the nodes. The function handles empty or single-node lists as a base case.
This recursive approach operates similarly to the iterative version but employs recursion to achieve insertion. It recursively inserts GCD nodes starting from the head of the linked list and processes each node until the end.
Time Complexity: O(n), where n is the size of the linked list.
Space Complexity: O(n) due to the stack space used in recursion.
1class ListNode:
2 def __init__(self,
The Python recursive solution inserts the GCD nodes between each pair of nodes in the linked list. The recursion base case is reached when there's either one node or no nodes left to process. By handling nodes recursively, the function continues until the entire list is processed.