2807. Insert Greatest Common Divisors in Linked List
Problem Description
The problem requires us to modify a given singly linked list by inserting new nodes. Specifically, for every two adjacent nodes in the list, we need to insert a new node between them. The value of this new node is not just any number but the greatest common divisor (GCD) of the values of these two adjacent nodes. The GCD of two numbers is the largest number that divides both of them without leaving a remainder.
For example, if our linked list is 1 -> 4 -> 3 -> 8
, then after inserting new nodes, it should look like 1 -> 1 -> 4 -> 1 -> 3 -> 1 -> 8
, where the numbers 1
, 1
, and 1
are the GCDs of 1 and 4
, 4 and 3
, 3 and 8
respectively. Note that if the GCD is 1
, it means that the two numbers are coprime (they have no common divisor other than 1
).
Intuition
For solving this problem, we need to traverse the linked list and calculate the GCD of every two adjacent values. We do not need any extra space besides the new nodes that we are inserting, and we can do the insertion in a single pass through the list.
The steps involve:
- Start by pointing to the first node of the list.
- While we have not reached the end of the list (i.e., the current node's
next
is notNone
):- Calculate the GCD of the current node's value and the next node's value.
- Create a new node with the calculated GCD value.
- Insert this new node between the current node and the next node.
- Move to the next pair of nodes to continue the process.
We use a utility function, gcd
, which will calculate the greatest common divisor of two numbers. Python provides a built-in function for this in the [math](/problems/math-basics)
module, which could be employed to simplify our code. The process of inserting the new node involves manipulating the next
pointers of the nodes to accommodate the new GCD node in between.
Overall, this approach works because linked lists allow for efficient insertion operations since, unlike arrays, we do not need to shift elements after the insertion point. We can simply rewire the next
pointers appropriately to complete the insertion.
Learn more about Linked List and Math patterns.
Solution Approach
The solution involves manipulation of linked list nodes and calculating the greatest common divisor (GCD) between adjacent nodes. The steps below detail the algorithm used in the provided code:
-
Initialization: We initialize two pointers,
pre
andcur
. Thepre
holds the reference to the current node, where we will insert a new node after, andcur
holds the reference to the next node, which will be used for calculating GCD. Initially,pre
points tohead
andcur
points tohead.next
. -
Traversal and Insertion:
- We enter a loop that continues to iterate as long as
cur
is notNone
, meaning there are still nodes to process. - Inside the loop, we calculate the GCD of
pre.val
andcur.val
using a functiongcd
. This function is assumed to be predefined or imported from the[math](/problems/math-basics)
module in Python (from math import gcd
). - We create a new
ListNode
with the calculated GCD, and itsnext
points tocur
. This effectively creates a new node betweenpre
andcur
. - Next, we rewire the
next
pointer of thepre
node to point to the new node. - We update the
pre
pointer to now point to thecur
node, since we've finished inserting the new node after whatpre
was pointing to before. - Lastly, we update
cur
to point tocur.next
, moving forward in the linked list to the next pair of nodes.
- We enter a loop that continues to iterate as long as
-
Algorithm Pattern: The approach here doesn't use extra space for an auxiliary data structure but directly works on the list itself, modifying pointers as needed. It's an in-place algorithm with respect to linked list manipulation, although new nodes are created for storing the GCDs.
-
GCD Function: The GCD function utilized is a key part of this solution, which calculates the greatest common divisor of two given numbers. If Python's built-in
gcd
function is not being used, an implementation of the Euclidean algorithm would typically be employed.
This implementation's time complexity is O(n * log(max(A))), where n
is the number of nodes in the list and log(max(A))
represents the time complexity of computing the GCD for any two numbers in the list (assuming A
is the set of integers in the nodes). The space complexity is O(1) ignoring the space taken by the output list; in a more practical sense, considering the new nodes, it would be O(n) due to the new nodes being inserted into the linked list.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let us consider a small linked list: 5 -> 10
. According to the problem, we need to find the GCD of every two adjacent nodes and insert a new node with that value in between them. In this case, we only need to find the GCD of 5 and 10. Using the Euclidean algorithm, we see that the GCD of 5 and 10 is 5.
Here is the step-by-step process based on the solution approach:
-
Initialization: We begin with two pointers,
pre
is pointing to the node with value 5 (head of the list), andcur
is pointing to the node with value 10 (head.next
). -
Traversal and Insertion:
- Since
cur
is notNone
, we enter the loop. - We compute the GCD of
pre.val
(5) andcur.val
(10), which is 5. - A new node is created with the GCD value 5, and its
next
is set to point tocur
(ListNode(5, cur)
). - We then update
pre.next
to point to this new node. The linked list now looks like5 -> 5 -> 10
. - We move
pre
to point tocur
, which is the node with the value 10. cur
is updated tocur.next
, which isNone
(end of the list).
- Since
By end of these steps, the traversal and insertion phase is complete, as there are no more nodes to process. The final linked list after the GCD insertion is 5 -> 5 -> 10
. It must be noted that if the linked list were longer, we would continue the process until we reach the end of the list.
-
Algorithm Pattern: In our example, we traversed the list and inserted the nodes without any extra data structures or modification of the original nodes' values. We only changed the
next
pointers to accommodate the new nodes. -
GCD Function: The GCD value was calculated using the known algorithm, or we could have used Python's built-in
gcd
function for simplification (from math import gcd
).
This example demonstrates the workings of our approach on a very small linked list. For linked lists with more nodes, the method would continue analogously until every pair of adjacent nodes has been processed.
Solution Implementation
1from math import gcd
2
3# Definition for singly-linked list.
4class ListNode:
5 def __init__(self, val=0, next_node=None):
6 self.val = val
7 self.next = next_node
8
9class Solution:
10 def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
11 # Initialize pointers: 'prev_node' pointing to the current node being processed,
12 # and 'current_node' pointing to the next node in the list.
13 prev_node, current_node = head, head.next
14
15 # Iterate through the linked list until we reach the end.
16 while current_node:
17 # Compute Greatest Common Divisor (GCD) of the values in the 'prev_node' and 'current_node'.
18 gcd_value = gcd(prev_node.val, current_node.val)
19
20 # Insert a new node with the GCD value between the 'prev_node' and 'current_node'.
21 prev_node.next = ListNode(gcd_value, current_node)
22
23 # Update pointers: move 'prev_node' to the 'current_node' and
24 # 'current_node' to the next node in the list.
25 prev_node, current_node = current_node, current_node.next
26
27 # Return the modified linked list head.
28 return head
29
1/**
2 * Definition for singly-linked list.
3 */
4class ListNode {
5 int val;
6 ListNode next;
7 ListNode() {}
8 ListNode(int val) { this.val = val; }
9 ListNode(int val, ListNode next) { this.val = val; this.next = next; }
10}
11
12public class Solution {
13
14 /**
15 * Inserts a new node with the value of the greatest common divisor
16 * between each pair of adjacent nodes in the linked list.
17 *
18 * @param head The head of the singly-linked list.
19 * @return The head of the modified linked list, with new nodes added.
20 */
21 public ListNode insertGreatestCommonDivisors(ListNode head) {
22 // Initialize two pointers for traversing the link list.
23 ListNode prev = head;
24 ListNode curr = head.next;
25
26 // Iterate over the list until we reach the end.
27 while (curr != null) {
28 // Get the greatest common divisor of the values in the two nodes.
29 int gcdValue = gcd(prev.val, curr.val);
30
31 // Insert a new node with the GCD value between the two nodes.
32 prev.next = new ListNode(gcdValue, curr);
33
34 // Move the pointers forward to the next pair of nodes.
35 prev = curr;
36 curr = curr.next;
37 }
38
39 // Return the unchanged head of the modified list.
40 return head;
41 }
42
43 /**
44 * Helper function to calculate the greatest common divisor of two integers.
45 *
46 * @param a The first integer.
47 * @param b The second integer.
48 * @return The greatest common divisor of a and b.
49 */
50 private int gcd(int a, int b) {
51 // If the second number, b, is 0, return the first number, a.
52 if (b == 0) {
53 return a;
54 }
55 // Keep calling the gcd function recursively, reducing the problem size.
56 return gcd(b, a % b);
57 }
58}
59
1#include <algorithm> // Include algorithm header to use std::gcd
2
3// Definition for singly-linked list node.
4struct ListNode {
5 int val;
6 ListNode *next;
7 ListNode() : val(0), next(nullptr) {} // Default constructor
8 ListNode(int x) : val(x), next(nullptr) {} // Constructor initializing val
9 ListNode(int x, ListNode *next) : val(x), next(next) {} // Constructor initializing both val and next
10};
11
12class Solution {
13public:
14 // Function to insert nodes containing the Greatest Common Divisor (GCD) of the
15 // adjacent nodes' values, between those nodes in the list.
16 ListNode* insertGreatestCommonDivisors(ListNode* head) {
17 if (!head) return nullptr; // Return if the list is empty
18
19 ListNode* current = head; // Current node is set to the head of the list
20 ListNode* nextNode = head->next; // Next node is the one following current
21
22 // Iterate over each pair of adjacent nodes until the end of the list
23 while (nextNode) {
24 // Calculate GCD of the values in the current and next nodes
25 int gcdValue = std::gcd(current->val, nextNode->val);
26
27 // Insert a new node with calculated GCD value between current and next nodes
28 current->next = new ListNode(gcdValue, nextNode);
29
30 // Move to the next pair of nodes, skipping over the newly inserted node
31 current = nextNode;
32 nextNode = nextNode->next;
33 }
34 return head; // Return the updated list with inserted GCD nodes
35 }
36};
37
1// Type definition for a node in a singly-linked list.
2type ListNode = {
3 val: number;
4 next: ListNode | null;
5};
6
7/**
8 * Inserts the greatest common divisor (GCD) of the values of each pair of adjacent nodes into the list.
9 * @param head the head of the singly-linked list.
10 * @returns the modified list with GCD nodes inserted.
11 */
12function insertGreatestCommonDivisors(head: ListNode | null): ListNode | null {
13 // Pointers for the current and next node in the list
14 let currentNode = head;
15 let nextNode = head?.next;
16
17 // Loop through each pair of adjacent nodes in the list
18 while (nextNode) {
19 // Calculate the GCD of the values of currentNode and nextNode
20 const gcdValue = gcd(currentNode.val, nextNode.val);
21 // Insert a new node with the GCD value between the currentNode and nextNode
22 currentNode.next = { val: gcdValue, next: nextNode };
23 // Move the currentNode pointer to the next node in the original list
24 currentNode = nextNode;
25 // Move the nextNode pointer to the node following the nextNode in the original list
26 nextNode = nextNode.next;
27 }
28
29 return head;
30}
31
32/**
33 * Calculates the greatest common divisor (GCD) of two non-negative integers.
34 * @param a the first integer.
35 * @param b the second integer.
36 * @returns the GCD of a and b.
37 */
38function gcd(a: number, b: number): number {
39 if (b === 0) {
40 return a;
41 }
42 // Recursively call gcd with b and the remainder of a divided by b
43 return gcd(b, a % b);
44}
45
Time and Space Complexity
Time Complexity
The time complexity of the given algorithm is determined by how many times it iterates through the linked list and how many times it computes the greatest common divisor (gcd) for adjacent nodes.
-
The algorithm traverses each node of the linked list once to insert the computed gcds. If there are
n
nodes in the list, it makesn-1
computations of gcd because we compute gcd for every pair of adjacent nodes. -
The time complexity of the
gcd
function depends on the values of the nodes. The worst-case scenario for Euclid's algorithm is when the two numbers are consecutive Fibonacci numbers, which leads to a time complexity ofO(log(min(a, b)))
wherea
andb
are the values of the nodes.
Combining these two factors, the overall time complexity of the algorithm is O(n * log(min(a, b)))
.
Space Complexity
- The space complexity is determined by the additional space needed by the algorithm which is not part of the input. In this case, we are inserting
n-1
new nodes to store the gcds, this requiresO(n)
additional space.
Therefore, the space complexity of the algorithm is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
Linked List Cycle Given a linked list with potentially a loop determine whether the linked list from the first node contains a cycle in it For bonus points do this with constant space Parameters nodes The first node of a linked list with potentially a loop Result Whether there is a loop contained
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!