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 constructor(val, next = null) {
3 this.val = val;
4 this.next = next;
5 }
6}
7
8function insertGcds(head) {
9 if (!head || !head.next) return head;
10
11 let current = head;
12 while (current && current.next) {
13 let gcdValue = gcd(current.val, current.next.val);
14 let newNode = new ListNode(gcdValue);
15 newNode.next = current.next;
16 current.next = newNode;
17 current = newNode.next;
18 }
19 return head;
20}
21
22function gcd(a, b) {
23 return b === 0 ? a : gcd(b, a % b);
24}This JavaScript solution iteratively traverses the linked list, computing the GCD for each pair of nodes with a helper function and inserting new nodes in between. The usage of ListNode encapsulates the linked list node structure.
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.