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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode* next;
7};
8
9int compute_gcd(int a, int b) {
10 if (b == 0) return a;
11 return compute_gcd(b, a % b);
12}
13
14struct ListNode* insertGcds(struct ListNode* head) {
15 if (!head || !(head->next)) return head;
16
17 struct ListNode* current = head;
18 while (current && current->next) {
19 int gcdValue = compute_gcd(current->val, current->next->val);
20 struct ListNode* newNode = (struct ListNode*)malloc(sizeof(struct ListNode));
21 newNode->val = gcdValue;
22 newNode->next = current->next;
23 current->next = newNode;
24 current = newNode->next;
25 }
26
27 return head;
28}The C solution uses a recursive function to compute the GCD and dynamically allocates new nodes with GCD values between adjacent nodes. It ensures memory management using malloc.
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.