Medium

题目描述

给你一个链表的头节点 head，其中每个节点包含一个整数值。

在每对相邻节点之间，插入一个新节点，新节点的值等于这两个相邻节点值的最大公约数。

返回插入后的链表。

两个数的最大公约数是能够同时整除这两个数的最大正整数。

示例 1：

输入：head = [18,6,10,3]
输出：[18,6,6,2,10,1,3]
解释：第1个图表示初始链表，第2个图表示插入新节点后的链表（蓝色节点是插入的节点）。
- 我们在第1个和第2个节点之间插入18和6的最大公约数6。
- 我们在第2个和第3个节点之间插入6和10的最大公约数2。
- 我们在第3个和第4个节点之间插入10和3的最大公约数1。
没有更多相邻节点，所以我们返回链表。

示例 2：

输入：head = [7]
输出：[7]
解释：第1个图表示初始链表，第2个图表示插入新节点后的链表。
没有相邻节点对，所以我们返回初始链表。

提示：

  • 链表中节点的数量在范围 [1, 5000] 内
  • 1 <= Node.val <= 1000

解题思路

这道题的核心是在链表的相邻节点间插入新节点，新节点的值为相邻两节点值的最大公约数（GCD）。

思路分析：

  1. 遍历链表：从头节点开始，遍历链表中的每一对相邻节点。

  2. 计算GCD：对于每一对相邻节点，计算它们值的最大公约数。可以使用欧几里得算法（辗转相除法）来高效计算GCD。

  3. 插入新节点：在当前节点和下一个节点之间插入一个新节点，新节点的值为计算得到的GCD。

  4. 更新指针：插入新节点后，需要正确更新指针关系，确保链表结构完整。

算法步骤：

  • 如果链表只有一个节点，直接返回
  • 遍历链表，对于每个节点curr，如果curr.next存在：
    • 计算gcd(curr.val, curr.next.val)
    • 创建新节点，值为计算得到的GCD
    • 将新节点插入curr和curr.next之间
    • 移动curr指针到新插入的节点的下一个节点（原来的curr.next）

这种方法只需要一次遍历，时间复杂度为O(n)，其中n是原链表的节点数。

代码实现

class Solution {
private:
    int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        
        ListNode* curr = head;
        while (curr->next) {
            int gcdVal = gcd(curr->val, curr->next->val);
            ListNode* newNode = new ListNode(gcdVal);
            newNode->next = curr->next;
            curr->next = newNode;
            curr = newNode->next;
        }
        
        return head;
    }
};

class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        import math
        
        if not head or not head.next:
            return head
        
        curr = head
        while curr.next:
            gcd_val = math.gcd(curr.val, curr.next.val)
            new_node = ListNode(gcd_val)
            new_node.next = curr.next
            curr.next = new_node
            curr = new_node.next
        
        return head

public class Solution {
    private int GCD(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    public ListNode InsertGreatestCommonDivisors(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode curr = head;
        while (curr.next != null) {
            int gcdVal = GCD(curr.val, curr.next.val);
            ListNode newNode = new ListNode(gcdVal);
            newNode.next = curr.next;
            curr.next = newNode;
            curr = newNode.next;
        }
        
        return head;
    }
}

var insertGreatestCommonDivisors = function(head) {
    function gcd(a, b) {
        while (b !== 0) {
            let temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
    
    if (!head || !head.next) {
        return head;
    }
    
    let curr = head;
    while (curr.next) {
        const gcdVal = gcd(curr.val, curr.next.val);
        const newNode = new ListNode(gcdVal);
        newNode.next = curr.next;
        curr.next = newNode;
        curr = newNode.next;
    }
    
    return head;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × log(min(a,b)))n是链表节点数，log(min(a,b))是GCD计算的时间复杂度
空间复杂度O(1)只使用常数级额外空间（不包括新创建的节点）

相关题目