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.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int x) { val = x; }
5}
6
7public class Solution {
8 public ListNode InsertGcds(ListNode head) {
9 if (head == null || head.next == null) return head;
10
11 ListNode current = head;
12
13 while (current != null && current.next != null) {
14 int gcdValue = Gcd(current.val, current.next.val);
15 ListNode newNode = new ListNode(gcdValue);
16 newNode.next = current.next;
17 current.next = newNode;
18 current = newNode.next;
19 }
20
21 return head;
22 }
23
24 private int Gcd(int a, int b) {
25 return b == 0 ? a : Gcd(b, a % b);
26 }
27}This C# solution calculates the GCD for adjacent node values and inserts a new node between them. The Gcd helper method utilizes recursion.
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.