LeetCode Problem 2807

Difficulty: 🟡 Medium
Topics: Linked List, Math, Number Theory

Solution

LeetCode 2807 - Insert Greatest Common Divisors in Linked List

Problem Understanding

This problem gives us the head of a singly linked list where every node contains a positive integer. Our task is to modify the list by inserting a new node between every pair of adjacent nodes.

The value of each inserted node must be the greatest common divisor (GCD) of the two neighboring nodes. The GCD of two integers is the largest positive integer that divides both numbers without leaving a remainder.

For example, if two adjacent nodes contain 18 and 6, their GCD is 6, so we insert a new node with value 6 between them. If two adjacent nodes contain 10 and 3, their GCD is 1, so we insert a node containing 1.

The input consists of a linked list with between 1 and 5000 nodes. Each node value is between 1 and 1000.

The output should be the modified linked list after all required insertions have been performed.

The constraints are relatively small. A linked list of length 5000 is not large, and node values are at most 1000, making GCD computations very inexpensive. This suggests that a straightforward traversal of the linked list should be sufficient.

Several edge cases are important:

• A list containing only one node has no adjacent pair, so no insertion should occur.
• Adjacent values may already be equal. In that case, the GCD is the value itself.
• Adjacent values may be coprime, producing a GCD of 1.
• The implementation must correctly update pointers so that no nodes are lost during insertion.

Approaches

Brute Force Approach

A brute force solution could first copy all node values into an array. Then, for every adjacent pair in the array, compute the GCD and build an entirely new linked list containing both the original values and the inserted GCD values.

This approach is correct because it explicitly reconstructs the desired final sequence. However, it requires additional memory proportional to the size of the list. Since the original linked list can be modified directly, rebuilding everything is unnecessary.

Key Insight

The important observation is that each insertion only depends on two adjacent nodes.

While traversing the linked list, we always have access to the current node and its next node. Therefore, we can:

1. Compute the GCD of their values.
2. Create a new node containing that GCD.
3. Insert it directly between the two nodes.
4. Continue traversal from the original next node.

This allows us to modify the list in place using only constant extra space.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(n)	Copy values and rebuild an entirely new list
Optimal	O(n)	O(1)	Traverse once and insert GCD nodes in place

Algorithm Walkthrough

1. Start with a pointer called current at the head of the linked list.
2. Continue while both current and current.next exist. This ensures there is an adjacent pair available.
3. Let the two values be:

• current.val
• current.next.val

4. Compute the greatest common divisor of these two values using the Euclidean algorithm. Most languages provide a built-in GCD function.
5. Create a new node whose value is the computed GCD.
6. Store a reference to the original next node because we will need to reconnect the list after insertion.
7. Insert the new node:

• Set new_node.next to the original next node.
• Set current.next to new_node.

8. After insertion, move current to the original next node, not the newly inserted node. This ensures each original adjacent pair is processed exactly once.
9. Repeat until there is no next node remaining.
10. Return the original head of the linked list.

Why it works

At every step, the algorithm processes exactly one pair of adjacent original nodes. The GCD node is inserted between them without altering the relative order of any original nodes. After insertion, traversal jumps to the second original node, ensuring no pair is processed twice and no pair is skipped. Since every adjacent original pair receives exactly one inserted GCD node, the resulting linked list is precisely the required output.

Python Solution

from math import gcd
from typing import Optional

# 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]:
        current = head

        while current and current.next:
            next_node = current.next
            gcd_value = gcd(current.val, next_node.val)

            gcd_node = ListNode(gcd_value)
            current.next = gcd_node
            gcd_node.next = next_node

            current = next_node

        return head

The implementation begins by placing a pointer at the head of the linked list. While there is an adjacent node available, it computes the GCD of the two neighboring values.

The original next node is stored in next_node before modifying any pointers. A new node containing the GCD is then created and inserted between the current node and the original next node.

After insertion, traversal continues from the original next node. This is important because the newly inserted node should not participate in future GCD calculations. The process repeats until all original adjacent pairs have been handled.

Finally, the head of the modified linked list is returned.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func insertGreatestCommonDivisors(head *ListNode) *ListNode {
	current := head

	for current != nil && current.Next != nil {
		nextNode := current.Next
		gcdValue := gcd(current.Val, nextNode.Val)

		gcdNode := &ListNode{Val: gcdValue}

		current.Next = gcdNode
		gcdNode.Next = nextNode

		current = nextNode
	}

	return head
}

The Go implementation follows exactly the same logic as the Python version. Since Go does not provide a built-in integer GCD function in this context, we implement the Euclidean algorithm manually.

Pointer manipulation is explicit through *ListNode references. The traversal condition checks both current != nil and current.Next != nil before processing an adjacent pair.

Because node values are at most 1000, integer overflow is not a concern.

Worked Examples

Example 1

Input:

18 -> 6 -> 10 -> 3

Iteration Trace

Current Node	Next Node	GCD	List After Insertion
18	6	6	18 → 6 → 6 → 10 → 3
6	10	2	18 → 6 → 6 → 2 → 10 → 3
10	3	1	18 → 6 → 6 → 2 → 10 → 1 → 3

Final output:

18 -> 6 -> 6 -> 2 -> 10 -> 1 -> 3

Example 2

Input:

7

Iteration Trace

Current Node	Next Node Exists?	Action
7	No	Stop immediately

Final output:

7

No insertion occurs because there is no adjacent pair.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each original node pair is processed exactly once
Space	O(1)	Only a few pointer variables are used, excluding output nodes

The linked list is traversed one time. For a list containing n nodes, there are exactly n - 1 adjacent pairs, and each pair requires one GCD computation and one insertion. Since node values are bounded by 1000, each GCD computation is effectively constant time. Therefore, the overall running time is linear in the number of nodes.

The algorithm performs all modifications directly within the existing linked list structure and only uses a constant number of auxiliary variables, resulting in constant extra space usage.

Test Cases

# Helper functions assumed:
# build_list(values)
# linked_list_to_list(head)

sol = Solution()

# Example 1
head = build_list([18, 6, 10, 3])
result = sol.insertGreatestCommonDivisors(head)
assert linked_list_to_list(result) == [18, 6, 6, 2, 10, 1, 3]  # sample case

# Example 2
head = build_list([7])
result = sol.insertGreatestCommonDivisors(head)
assert linked_list_to_list(result) == [7]  # single node

# Two nodes with common divisor
head = build_list([12, 18])
result = sol.insertGreatestCommonDivisors(head)
assert linked_list_to_list(result) == [12, 6, 18]  # gcd = 6

# Two coprime nodes
head = build_list([8, 15])
result = sol.insertGreatestCommonDivisors(head)
assert linked_list_to_list(result) == [8, 1, 15]  # gcd = 1

# Equal values
head = build_list([5, 5])
result = sol.insertGreatestCommonDivisors(head)
assert linked_list_to_list(result) == [5, 5, 5]  # gcd equals value

# Multiple equal values
head = build_list([9, 9, 9])
result = sol.insertGreatestCommonDivisors(head)
assert linked_list_to_list(result) == [9, 9, 9, 9, 9]  # repeated insertions

# Increasing values
head = build_list([2, 4, 8, 16])
result = sol.insertGreatestCommonDivisors(head)
assert linked_list_to_list(result) == [2, 2, 4, 4, 8, 8, 16]  # varying gcds

# Maximum value range
head = build_list([1000, 1000])
result = sol.insertGreatestCommonDivisors(head)
assert linked_list_to_list(result) == [1000, 1000, 1000]  # upper bound values

# Mixed divisibility
head = build_list([21, 14, 35])
result = sol.insertGreatestCommonDivisors(head)
assert linked_list_to_list(result) == [21, 7, 14, 7, 35]  # gcds on both sides

Test Summary

Test	Why
[18,6,10,3]	Official example with multiple insertions
[7]	Single-node boundary case
[12,18]	Simple nontrivial GCD
[8,15]	Coprime values producing GCD 1
[5,5]	Equal adjacent values
[9,9,9]	Multiple repeated insertions
[2,4,8,16]	Consecutive divisible values
[1000,1000]	Upper bound node values
[21,14,35]	Different GCD computations in one traversal

Edge Cases

Single Node List

A list containing only one node has no adjacent pair. A common bug is attempting to access current.next without checking whether it exists. The loop condition while current and current.next prevents this problem and causes the algorithm to return the original list unchanged.

Coprime Adjacent Values

When two neighboring values share no common divisor larger than 1, the inserted node must contain 1. Some implementations incorrectly assume every inserted value will be greater than one. Using a proper GCD computation guarantees correct handling of pairs such as (8, 15).

Equal Adjacent Values

If two neighboring nodes contain the same value, the GCD equals that value itself. For example, (9, 9) produces an inserted node containing 9. The algorithm treats this naturally because the GCD function correctly returns the original value.

Pointer Updates During Insertion

The most subtle bug involves losing part of the linked list while inserting a node. If the original next node is not saved before rewiring pointers, the remainder of the list can become unreachable. The implementation stores next_node first, then reconnects pointers in the correct order:

current -> next_node

becomes

current -> gcd_node -> next_node

This guarantees the entire list remains connected throughout the traversal.