⚡Flashcard Drill➔
NeetCode #883LC-2807MediumMath & GeometryNC 250
← Back to All Problems

#883 · #2807 · Insert Greatest Common Divisors in Linked List(在链表中插入最大公约数)

📌 Problem Statement & Constraints

Given the head of a linked list whose nodes contain integers, insert a new node between every pair of adjacent nodes; the new node holds the greatest common divisor of the two neighbours. Return the head of the modified list. Constraints: 1 <= number of nodes <= 5000, 1 <= Node.val <= 1000.

💡 Core Algorithmic Approaches

  1. Walk the list with a single pointer, examining each adjacent pair.
  2. Compute the gcd of the two node values and create a node holding it.
  3. Splice the new node between them: point it at the second node, then point the first node at it.
  4. Advance the pointer to the node after the inserted one, so the newly inserted node is not itself paired again.

💻 Benchmark Python3 Implementation

class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        from math import gcd
        cur = head
        while cur and cur.next:
            g = gcd(cur.val, cur.next.val)
            node = ListNode(g)
            node.next = cur.next      # new node points at the right neighbour
            cur.next = node           # left neighbour points at the new node
            cur = node.next           # continue from the right neighbour
        return head

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log V): n insertions, each gcd costing O(log V) where V is the maximum value.
💾 Space Complexity
O(1) beyond the newly created nodes.

⚠️ Interview Pitfalls & Follow-ups

  • Advancing with cur = cur.next: that lands on the inserted node and the loop would pair it again.
  • Inserting before the head: the problem only asks for insertions between adjacent pairs.
  • Splicing in the wrong order: node.next must be set before cur.next, otherwise the rest of the list is lost.
  • Assuming at least two nodes: a single-node list is returned unchanged.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Math & Geometry Problems