Problem Description

You are given a linked list where each node contains an integer value. Your task is to modify the linked list by inserting new nodes between every pair of adjacent nodes.

For each pair of adjacent nodes in the original list, you need to:

1. Calculate the greatest common divisor (GCD) of their values
2. Create a new node with this GCD value
3. Insert this new node between the two adjacent nodes

The greatest common divisor of two numbers is the largest positive integer that divides both numbers evenly. For example, the GCD of 12 and 8 is 4, since 4 is the largest number that divides both 12 and 8 without a remainder.

The solution uses two pointers to traverse the list:

• pre points to the current node being processed
• cur points to the next node in the original list

The algorithm works by:

1. Starting with pre at the head and cur at the second node
2. While cur exists:
   • Calculate x = gcd(pre.val, cur.val)
   • Create a new node with value x and insert it between pre and cur
   • Move forward: set pre = cur and cur = cur.next
3. Return the modified linked list

For example, if the original list is [18] -> [6] -> [10] -> [3], the result would be [18] -> [6] -> [6] -> [2] -> [10] -> [1] -> [3], where 6 is the GCD of 18 and 6, 2 is the GCD of 6 and 10, and 1 is the GCD of 10 and 3.

Intuition

The key insight is that we need to traverse the linked list while maintaining references to consecutive pairs of nodes. Since we're inserting nodes between existing ones, we need to be careful not to lose track of the original nodes.

Think of it like walking along a chain where you need to add new links between every existing pair of links. You need two hands - one to hold the current link and another to hold the next link. After inserting a new link between them, you move forward by shifting your hands to the next pair.

The natural approach is to use two pointers:

• We can't just use a single pointer because we need access to both nodes in each pair to calculate their GCD
• We need pre to maintain our connection to the previous part of the list
• We need cur to know where to connect after inserting the new node

Why do we update pointers as pre = cur and cur = cur.next? After inserting a GCD node between pre and cur, the next pair to process is cur and whatever comes after cur. So cur becomes our new pre, and cur.next becomes our new cur.

The beauty of this approach is that we're modifying the list in-place during a single pass. We don't need extra space for a new list or need to traverse multiple times. Each insertion is done locally between two nodes, and we systematically move through the entire list.

The gcd function is used directly from Python's math library (imported as from math import gcd), which efficiently calculates the greatest common divisor using Euclid's algorithm.

Learn more about Linked List and Math patterns.

Solution Approach

The implementation follows a straightforward simulation approach using two pointers to traverse and modify the linked list.

Algorithm Steps:

1. Initialize two pointers: Set pre = head (pointing to the first node) and cur = head.next (pointing to the second node). This establishes our initial pair of adjacent nodes.

2. Traverse the list: Use a while cur: loop to process each pair of adjacent nodes until we reach the end of the list.

3. For each pair of nodes:

   • Calculate the GCD: x = gcd(pre.val, cur.val)
   • Create a new node with value x and insert it between pre and cur: pre.next = ListNode(x, cur)
     • The new node's value is x
     • The new node's next pointer points to cur
     • pre.next now points to this new node

4. Move to the next pair: Update pre = cur and cur = cur.next. This shifts our window forward - what was the second node in the pair becomes the first node of the next pair.

5. Return the modified list: Return head which still points to the beginning of the now-modified list.

Key Implementation Details:

• The insertion pre.next = ListNode(x, cur) effectively places the new GCD node between pre and cur by:

  • Making pre point to the new node
  • Making the new node point to cur

• The pointer updates pre, cur = cur, cur.next ensure we skip over the newly inserted node and continue processing original adjacent pairs.

• The loop naturally terminates when cur becomes None, which happens after processing the last pair of original nodes.

Time Complexity: O(n) where n is the number of nodes in the original list, as we visit each node once.

Space Complexity: O(1) if we don't count the output nodes. We only use two pointer variables regardless of input size.

Example Walkthrough

Let's walk through a small example with the linked list: [12] -> [8] -> [6]

Initial Setup:

• head points to node with value 12
• pre = head (points to 12)
• cur = head.next (points to 8)

First Iteration:

• We have the pair (12, 8)
• Calculate GCD: gcd(12, 8) = 4
• Create new node with value 4 and insert it between pre and cur:
  • pre.next = ListNode(4, cur)
  • This makes: [12] -> [4] -> [8] -> [6]
• Update pointers: pre = cur (now points to 8), cur = cur.next (now points to 6)

Second Iteration:

• We have the pair (8, 6)
• Calculate GCD: gcd(8, 6) = 2
• Create new node with value 2 and insert it between pre and cur:
  • pre.next = ListNode(2, cur)
  • This makes: [12] -> [4] -> [8] -> [2] -> [6]
• Update pointers: pre = cur (now points to 6), cur = cur.next (now None)

Termination:

• cur is None, so the while loop exits
• Return head, which points to the modified list

Final Result: [12] -> [4] -> [8] -> [2] -> [6]

Notice how we only process pairs from the original list. The newly inserted node with value 4 is never used in a GCD calculation - we skip over it by moving our pointers to the next original pair (8, 6).

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log M)

The algorithm traverses the linked list once, visiting each node exactly once, which takes O(n) time where n is the number of nodes in the linked list. At each node, we compute the GCD (Greatest Common Divisor) between two node values using the gcd function. The GCD operation using Euclidean algorithm has a time complexity of O(log M) where M is the maximum value among the two numbers being compared (or the maximum value in the entire linked list). Since we perform the GCD operation for each adjacent pair of nodes (which is n-1 times), the overall time complexity is O(n × log M).

Space Complexity: O(1) (excluding the output)

The algorithm uses only a constant amount of extra space with two pointer variables pre and cur to traverse the linked list. The new nodes created are part of the result linked list and are not counted as auxiliary space. If we were to count the space for the newly created nodes, it would be O(n) since we insert n-1 new nodes between the existing nodes. However, following the convention stated in the reference answer where the space consumption of the result linked list is ignored, the space complexity is O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Handling Single Node or Empty List

One common pitfall is not properly handling edge cases where the linked list has only one node or is empty. The current implementation would fail if head is None or if the list has only one node, as head.next would either cause an AttributeError or be None, making the while loop never execute.

Problem Example:

• Input: None (empty list) → Code crashes with AttributeError
• Input: [5] (single node) → Works but should be explicitly handled

Solution: Add a guard clause at the beginning:

def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
    # Handle edge cases: empty list or single node
    if not head or not head.next:
        return head
  
    prev_node, curr_node = head, head.next
    # ... rest of the code

2. Incorrect Pointer Movement

A common mistake is updating pointers incorrectly, such as:

# WRONG: This would skip nodes
prev_node = prev_node.next.next  # This would jump over the GCD node
curr_node = curr_node.next

or

# WRONG: This would process the newly inserted node
prev_node = prev_node.next  # This points to the GCD node, not the original node
curr_node = curr_node.next

Solution: Always move prev_node to where curr_node was, ensuring we process original adjacent pairs:

# CORRECT
prev_node, curr_node = curr_node, curr_node.next

3. Creating Circular References

When inserting nodes, be careful not to create circular references:

# WRONG: Could create a cycle if not careful
new_node = ListNode(gcd_value)
new_node.next = curr_node
prev_node.next = new_node
# If we accidentally set curr_node.next = new_node somewhere, we'd have a cycle

Solution: Use the ListNode constructor that sets both value and next pointer atomically:

# CORRECT and safer
prev_node.next = ListNode(gcd_value, curr_node)

4. GCD Implementation Assumptions

The code uses math.gcd() which handles negative numbers and zero correctly in Python 3.5+, but if implementing GCD manually or using older Python versions, edge cases need consideration:

• GCD of 0 and any number n is |n|
• GCD of negative numbers should return positive result

Solution: Either use math.gcd() (recommended) or implement a robust GCD function:

def gcd(a, b):
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a if a else 1  # or handle 0,0 case as needed