2807。在链表中插入最大公约数
难度:中等
主题:链表、数学、数论
给定一个链表头,其中每个节点都包含一个整数值。
在每对相邻节点之间,插入一个新节点,其值等于它们的最大公约数。
返回插入后的链表.
两个数的最大公约数是能整除两个数的最大正整数。
示例1:
示例2:
示例 3:
约束:
提示:
解决方案:
我们需要在链表中的每对相邻节点之间插入节点。插入节点的值应该是两个相邻节点值的最大公约数(GCD)。我们将遍历链表,计算每对相邻节点的 GCD,然后相应地插入新节点。
以下是解决此问题的方法:
让我们用 PHP 实现这个解决方案:2807。在链表中插入最大公约数
<?php // Definition for a singly-linked list node. class ListNode { public $val = 0; public $next = null; public function __construct($val = 0, $next = null) { $this->val = $val; $this->next = $next; } } /** * Function to calculate the GCD of two numbers. * * @param $a * @param $b * @return mixed */ function gcd($a, $b) { ... ... ... /** * go to ./solution.php */ } /** * @param ListNode $head * @return ListNode */ function insertGreatestCommonDivisors($head) { ... ... ... /** * go to ./solution.php */ } /** * Function to print the linked list for testing purposes. * * @param $head * @return void */ function printList($head) { $current = $head; while ($current != null) { echo $current->val . " "; $current = $current->next; } echo "\n"; } // Example usage: // Create the linked list: 18 -> 6 -> 10 -> 3 $head = new ListNode(18); $head->next = new ListNode(6); $head->next->next = new ListNode(10); $head->next->next->next = new ListNode(3); // Insert GCD nodes. $modifiedHead = insertGreatestCommonDivisors($head); // Print the modified linked list. printList($modifiedHead); // Output should be: 18 -> 6 -> 6 -> 2 -> 10 -> 1 -> 3 ?>
ListNode 类:该类表示链表中节点的结构,具有值 ($val) 和下一个节点 ($next) 的属性。
GCD 计算:gcd 函数使用欧几里德算法计算两个整数的最大公约数。
主要逻辑(插入最大公约数):
边缘情况:如果列表只有一个节点,我们将按原样返回它,不做任何更改,因为没有相邻节点。
测试:函数 printList 是一个辅助函数,用于输出链表的值以进行验证。
For the input list [18, 6, 10, 3], the output is:
18 -> 6 -> 6 -> 2 -> 10 -> 1 -> 3
Contact Links
If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!
If you want more helpful content like this, feel free to follow me:
以上是在链表中插入最大公约数的详细内容。更多信息请关注PHP中文网其他相关文章!