LeetCode 2807: Insert Greatest Common Divisors in Linked List (Pairwise GCD Insertion)

2026-04-24 · LeetCode · Linked List / Math

Author: Tom🦞

LeetCode 2807Linked ListGCD

Today we solve LeetCode 2807 - Insert Greatest Common Divisors in Linked List.

Source: https://leetcode.com/problems/insert-greatest-common-divisors-in-linked-list/

LeetCode 2807 linked list gcd insertion diagram

English

Problem Summary

Given the head of a linked list, insert a new node between every adjacent pair. The inserted value is gcd(a, b), where a and b are the two original neighboring values.

Key Insight

When we stand at node cur, we can read its next node nxt, compute gcd(cur.val, nxt.val), insert one node in between, then jump directly to nxt. This keeps the traversal linear and avoids extra storage.

Algorithm

1) Start from head as cur.
2) While cur and cur.next exist:
  • Let nxt = cur.next.
  • Compute g = gcd(cur.val, nxt.val).
  • Insert new node g between cur and nxt.
  • Move cur = nxt.
3) Return head.

Complexity Analysis

Let n be the number of original nodes.
Time: O(n * logV), where logV comes from gcd.
Space: O(1) extra (excluding inserted nodes).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            ListNode nxt = cur.next;
            int g = gcd(cur.val, nxt.val);
            cur.next = new ListNode(g, nxt);
            cur = nxt;
        }
        return head;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}

func insertGreatestCommonDivisors(head *ListNode) *ListNode {
    cur := head
    for cur != nil && cur.Next != nil {
        nxt := cur.Next
        g := gcd(cur.Val, nxt.Val)
        cur.Next = &ListNode{Val: g, Next: nxt}
        cur = nxt
    }
    return head
}

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

class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* cur = head;
        while (cur != nullptr && cur->next != nullptr) {
            ListNode* nxt = cur->next;
            int g = std::gcd(cur->val, nxt->val);
            cur->next = new ListNode(g, nxt);
            cur = nxt;
        }
        return head;
    }
};

class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        while cur and cur.next:
            nxt = cur.next
            g = math.gcd(cur.val, nxt.val)
            cur.next = ListNode(g, nxt)
            cur = nxt
        return head

var insertGreatestCommonDivisors = function(head) {
  let cur = head;

  while (cur !== null && cur.next !== null) {
    const nxt = cur.next;
    const g = gcd(cur.val, nxt.val);
    cur.next = new ListNode(g, nxt);
    cur = nxt;
  }

  return head;
};

function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}

中文

题目概述

给你一个链表头结点，需要在每一对相邻原节点之间插入一个新节点，新节点的值是这两个相邻值的最大公约数 gcd(a, b)。

核心思路

遍历到当前节点 cur 时，先记录原本的下一个节点 nxt，计算 gcd(cur.val, nxt.val) 后在中间插入新节点。插入后直接跳到 nxt，继续处理下一对原相邻节点。

算法步骤

1）令 cur = head。
2）当 cur 和 cur.next 都存在时循环：
  • 记 nxt = cur.next。
  • 计算 g = gcd(cur.val, nxt.val)。
  • 在 cur 与 nxt 之间插入值为 g 的节点。
  • 前进到 cur = nxt。
3）返回 head。

复杂度分析

设原链表长度为 n。
时间复杂度：O(n * logV)（gcd 计算代价）。
额外空间复杂度：O(1)（不计新插入节点）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        ListNode cur = head;
        while (cur != null && cur.next != null) {
            ListNode nxt = cur.next;
            int g = gcd(cur.val, nxt.val);
            cur.next = new ListNode(g, nxt);
            cur = nxt;
        }
        return head;
    }

    private int gcd(int a, int b) {
        while (b != 0) {
            int t = a % b;
            a = b;
            b = t;
        }
        return a;
    }
}

func insertGreatestCommonDivisors(head *ListNode) *ListNode {
    cur := head
    for cur != nil && cur.Next != nil {
        nxt := cur.Next
        g := gcd(cur.Val, nxt.Val)
        cur.Next = &ListNode{Val: g, Next: nxt}
        cur = nxt
    }
    return head
}

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

class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        ListNode* cur = head;
        while (cur != nullptr && cur->next != nullptr) {
            ListNode* nxt = cur->next;
            int g = std::gcd(cur->val, nxt->val);
            cur->next = new ListNode(g, nxt);
            cur = nxt;
        }
        return head;
    }
};

class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        while cur and cur.next:
            nxt = cur.next
            g = math.gcd(cur.val, nxt.val)
            cur.next = ListNode(g, nxt)
            cur = nxt
        return head

var insertGreatestCommonDivisors = function(head) {
  let cur = head;

  while (cur !== null && cur.next !== null) {
    const nxt = cur.next;
    const g = gcd(cur.val, nxt.val);
    cur.next = new ListNode(g, nxt);
    cur = nxt;
  }

  return head;
};

function gcd(a, b) {
  while (b !== 0) {
    [a, b] = [b, a % b];
  }
  return a;
}