Insert Greatest Common Divisors in Linked List

Med

#2511Time: O(N * log(K)), where N is the number of nodes in the original list and K is the maximum value in a node. We traverse the original list once, and each step involves a GCD calculation.Space: O(1). We modify the list in-place. The space for the new nodes is part of the output structure and is not considered extra auxiliary space. The only extra space is for a few pointers and variables, which is constant.

Patterns

Math Number Theory

Data structures

Linked List

Prompt

Given the head of a linked list head, in which each node contains an integer value.

Between every pair of adjacent nodes, insert a new node with a value equal to the greatest common divisor of them.

Return the linked list after insertion.

The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.

Example 1:

Input: head = [18,6,10,3]
Output: [18,6,6,2,10,1,3]
Explanation: The 1st diagram denotes the initial linked list and the 2nd diagram denotes the linked list after inserting the new nodes (nodes in blue are the inserted nodes).
- We insert the greatest common divisor of 18 and 6 = 6 between the 1st and the 2nd nodes.
- We insert the greatest common divisor of 6 and 10 = 2 between the 2nd and the 3rd nodes.
- We insert the greatest common divisor of 10 and 3 = 1 between the 3rd and the 4th nodes.
There are no more adjacent nodes, so we return the linked list.

Example 2:

Input: head = [7]
Output: [7]
Explanation: The 1st diagram denotes the initial linked list and the 2nd diagram denotes the linked list after inserting the new nodes.
There are no pairs of adjacent nodes, so we return the initial linked list.

Constraints:

The number of nodes in the list is in the range [1, 5000].
1 <= Node.val <= 1000

Approaches

2 approaches with complexity analysis and trade-offs.

A more optimal approach in terms of space complexity is to modify the list in-place. We traverse the list, and for each adjacent pair of nodes, we create the new GCD node and insert it between them by rearranging the next pointers.

Algorithm

Initialize a pointer current = head.
If the list is empty or has only one node, no insertions are needed, so return head.
Iterate through the list with the condition while (current.next != null):
- a. Store the reference to the next node: nextNode = current.next.
- b. Calculate the GCD of current.val and nextNode.val.
- c. Create a new ListNode with the GCD value.
- d. Rewire the pointers to insert the new node: current.next = newNode and newNode.next = nextNode.
- e. Move current to the next node of the original list to process the next pair: current = nextNode.
Return the original head, which now points to the modified list.

Walkthrough

We traverse the list with a pointer, let's call it current, starting at the head. The loop continues as long as current.next is not null, ensuring we can always form a pair (current, current.next). In each iteration, we first get a handle on the node after current, let's call it nextNode. Then, we compute the GCD of current.val and nextNode.val. A new node is created with this GCD value. This new node is inserted between current and nextNode by setting current.next to the new node, and the new node's next to nextNode. Finally, to proceed to the next pair of original nodes, we advance current to nextNode. The process repeats until the end of the list is reached.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode insertGreatestCommonDivisors(ListNode head) {13        if (head == null || head.next == null) {14            return head;15        }16 17        ListNode current = head;18        while (current.next != null) {19            ListNode nextNode = current.next;20            21            // Calculate GCD22            int gcdVal = gcd(current.val, nextNode.val);23            24            // Create and insert the new node25            ListNode newNode = new ListNode(gcdVal);26            newNode.next = nextNode;27            current.next = newNode;28            29            // Move to the next original node30            current = nextNode;31        }32        33        return head;34    }35 36    // Helper function to calculate GCD using Euclidean algorithm37    private int gcd(int a, int b) {38        while (b != 0) {39            int temp = b;40            b = a % b;41            a = temp;42        }43        return a;44    }45}

Complexity

Time

O(N * log(K)), where N is the number of nodes in the original list and K is the maximum value in a node. We traverse the original list once, and each step involves a GCD calculation.

Space

O(1). We modify the list in-place. The space for the new nodes is part of the output structure and is not considered extra auxiliary space. The only extra space is for a few pointers and variables, which is constant.

Trade-offs

Pros

Extremely space-efficient, using only O(1) auxiliary space.
Avoids the overhead of allocating an entire new list.

Cons

Modifies the input list, which might be a side effect to avoid in some applications.

This straightforward approach involves iterating through the original linked list and building a completely new list that includes the original nodes and the new GCD nodes. It's easier to reason about but uses more memory.

Algorithm

Handle the edge case where the list has 0 or 1 node by returning head.
Create a dummy node to serve as the starting point of the new list. A tail pointer is used to track the end of the new list.
Initialize a current pointer to the head of the original list.
Iterate while current is not null:
- a. Create a new node with current.val and append it to the new list: tail.next = new ListNode(current.val); tail = tail.next;.
- b. If current.next is not null, it means there is an adjacent pair.
  - i. Calculate the GCD of current.val and current.next.val.
  - ii. Create a new node with the GCD value and append it to the new list: tail.next = new ListNode(gcd); tail = tail.next;.
- c. Advance current to the next node in the original list.
Return dummy.next.

Walkthrough

We initialize a new list with a dummy head to simplify appending nodes. We then traverse the input list from head to tail. For each node we encounter, we first append a copy of it to our new list. Then, we check if this node has a successor in the original list. If it does, we calculate the GCD of the current node's value and its successor's value. A new node containing this GCD is then created and appended to our new list. This process is repeated until all nodes from the original list have been processed. The final result is the list starting from the node after our dummy head.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode insertGreatestCommonDivisors(ListNode head) {13        if (head == null || head.next == null) {14            return head;15        }16 17        ListNode dummy = new ListNode(-1);18        ListNode tail = dummy;19        ListNode current = head;20 21        while (current != null) {22            // Add the original node23            tail.next = new ListNode(current.val);24            tail = tail.next;25 26            // If there is a next node, calculate GCD and insert27            if (current.next != null) {28                int gcdVal = gcd(current.val, current.next.val);29                tail.next = new ListNode(gcdVal);30                tail = tail.next;31            }32            current = current.next;33        }34 35        return dummy.next;36    }37 38    // Helper function to calculate GCD using Euclidean algorithm39    private int gcd(int a, int b) {40        while (b != 0) {41            int temp = b;42            b = a % b;43            a = temp;44        }45        return a;46    }47}

Complexity

Time

O(N * log(K)), where N is the number of nodes in the list and K is the maximum value in a node. The traversal takes O(N) time, and for each of the N-1 pairs, we perform a GCD calculation which takes O(log(K)) time.

Space

O(N), where N is the number of nodes in the original list. We create a new list of size `2N - 1`, which requires `O(N)` additional space.

Trade-offs

Pros

Simple logic, easy to understand and implement.
Preserves the original linked list, which can be an advantage.

Cons

Requires O(N) extra space to store the new list, making it less memory-efficient than an in-place solution.

Solutions

Solution

1/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode insertGreatestCommonDivisors ( ListNode head ) { for ( ListNode pre = head , cur = head . next ; cur != null ; cur = cur . next ) { int x = gcd ( pre . val , cur . val ); pre . next = new ListNode ( x , cur ); pre = cur ; } return head ; } private int gcd ( int a , int b ) { if ( b == 0 ) { return a ; } return gcd ( b , a % b ); } }

1/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * insertGreatestCommonDivisors ( ListNode * head ) { ListNode * pre = head ; for ( ListNode * cur = head -> next ; cur ; cur = cur -> next ) { int x = gcd ( pre -> val , cur -> val ); pre -> next = new ListNode ( x , cur ); pre = cur ; } return head ; } };

1# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def insertGreatestCommonDivisors ( self , head : Optional [ ListNode ] ) -> Optional [ ListNode ]: pre , cur = head , head . next while cur : x = gcd ( pre . val , cur . val ) pre . next = ListNode ( x , cur ) pre , cur = cur , cur . next return head

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem