연결리스트에 최대 공약수 삽입

<?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
?>




<h3>
  
  
  설명:
</h3>

<ol>
<li><p><strong>ListNode 클래스</strong>: 이 클래스는 값($val)과 다음 노드($next)에 대한 속성을 사용하여 연결된 목록의 노드 구조를 나타냅니다.</p></li>
<li><p><strong>GCD 계산</strong>: gcd 함수는 유클리드 알고리즘을 사용하여 두 정수의 최대 공약수를 계산합니다.</p></li>
<li>
<p><strong>메인 로직(insertGreatestCommonDivisors)</strong>:</p>

<ul>
<li>마지막에서 두 번째 노드에 도달할 때까지 연결 목록을 반복합니다.</li>
<li>인접 노드의 각 쌍에 대해 해당 값의 GCD를 계산합니다.</li>
<li>이 GCD 값으로 새 노드를 생성하고 현재 노드와 다음 노드 사이에 삽입합니다.</li>
</ul>
</li>
<li><p><strong>Edge Case</strong>: 리스트에 노드가 하나만 있는 경우 인접한 노드가 없으므로 변경하지 않고 그대로 반환합니다.</p></li>
<li><p><strong>테스트</strong>: printList 함수는 확인을 위해 연결된 목록의 값을 출력하는 데 사용되는 도우미 함수입니다.</p></li>
</ol>

<h3>
  
  
  Time Complexity:
</h3>

<ul>
<li>The time complexity of this solution is (O(n)), where (n) is the number of nodes in the linked list. Calculating the GCD for each adjacent pair takes constant time on average, and we perform a linear traversal of the list.</li>
</ul>

<h3>
  
  
  Example:
</h3>

<p>For the input list [18, 6, 10, 3], the output is:<br>
</p>

<pre class="brush:php;toolbar:false">18 -> 6 -> 6 -> 2 -> 10 -> 1 -> 3