javascript 解法, 执行用时: 92 ms, 内存消耗: 56.5 MB, 提交时间: 2024-01-06 00:51:16

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var insertGreatestCommonDivisors = function(head) {
    let node = head
    while (node.next != null) {
        node.next = new ListNode(gcd(node.val, node.next.val), node.next);
        node = node.next.next;
    }
    return head;
};

let gcd = (a, b) => b == 0 ? a : gcd(b, a % b);

php 解法, 执行用时: 20 ms, 内存消耗: 22.1 MB, 提交时间: 2023-08-07 15:24:53

/**
 * Definition for a singly-linked list.
 * class ListNode {
 *     public $val = 0;
 *     public $next = null;
 *     function __construct($val = 0, $next = null) {
 *         $this->val = $val;
 *         $this->next = $next;
 *     }
 * }
 */
class Solution {

    /**
     * @param ListNode $head
     * @return ListNode
     */
    function insertGreatestCommonDivisors($head) {
        $cur = $head;
        while ( $cur->next ) {
            $cur->next = new ListNode($this->gcd($cur->val, $cur->next->val), $cur->next);
            $cur = $cur->next->next;
        }
        return $head;
    }
    
    function gcd($a, $b) {
        while ( $a != 0 ) {
            $temp = $a;
            $a = $b % $a;
            $b = $temp;
        }
        return $b;
    }
}

java 解法, 执行用时: 2 ms, 内存消耗: 42.6 MB, 提交时间: 2023-08-07 15:18:28

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode insertGreatestCommonDivisors(ListNode head) {
        // 开始进行链表的操作
        ListNode node = head;
        while(node!=null&&node.next!=null) {
            ListNode next = node.next;
            // 开始在两个节点之间插入最大公约数进行处理
            int gd = gcd(node.val, next.val);
            ListNode newNode = new ListNode(gd);
            node.next = newNode;
            newNode.next = next;
            node = next;
        }

        return head;
    }

    private int gcd(int a, int b) {
        if(a%b==0) return b;
        else return gcd(b, a%b);
    }
}

cpp 解法, 执行用时: 60 ms, 内存消耗: 29.4 MB, 提交时间: 2023-08-07 15:17:47

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
       ListNode *a = head, *b = head->next;
        while (b != nullptr) {
            // 把节点 a 和 b 的 gcd 插到 ab 中间
            ListNode *node = new ListNode(gcd(a->val, b->val), b);
            a->next = node;
            // a 和 b 分别向后移动一个节点
            a = b; b = b->next;
        }
        return head; 
    }
};

golang 解法, 执行用时: 12 ms, 内存消耗: 6.2 MB, 提交时间: 2023-08-07 15:16:56

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func insertGreatestCommonDivisors(head *ListNode) *ListNode {
    cur := head
	for cur.Next != nil {
		cur.Next = &ListNode{gcd(cur.Val, cur.Next.Val), cur.Next}
		cur = cur.Next.Next
	}
	return head
}

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

python3 解法, 执行用时: 88 ms, 内存消耗: 20.3 MB, 提交时间: 2023-08-07 15:15:50

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

'''
遍历链表，在当前节点 cur 后面插入 gcd 节点，gcd 节点指向 cur 的下一个节点。
插入后，cur 更新为 cur.next.next。
循环直到 cur 没有下一个节点为止。
'''
class Solution:
    def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
        cur = head
        while cur.next:
            cur.next = ListNode(gcd(cur.val, cur.next.val), cur.next)
            cur = cur.next.next
        return head