[LeetCode] 2807. Insert Greatest Common Divisors in Linked List

https://leetcode.com/problems/insert-greatest-common-divisors-in-linked-list/description/?envType=daily-question&envId=2024-09-10

leetcode - Insert Greatest Common Divisors in Linked List

문제 유형 : 연결리스트

문제 난이도 : Medium

 

문제

Given the head of a linked list head, in which each node contains an integer value.

Between every pair of adjacent nodes, insert a new node with a value equal to the greatest common divisor of them.

Return the linked list after insertion.

The greatest common divisor of two numbers is the largest positive integer that evenly divides both numbers.

 

정수 값을 담은 연결리스트의 head가 주어진다.

두 인접한 노드들 사이에, 최대공약수를 끼워넣어서 변형된 연결리스트의 head를 반환하시오.

 

 

풀이

현재 순회중이 노드와 그 다음노드를 동시에 참조해야 한다.

최대공약수를 구해서 새로 노드를 하나 만든다.

현재 노드의 next를 새 노드로, 새 노드의 next를 기존 다음노드로 한다.

현재 노드를 기존 다음노드로 하고, 기존 다음노드는 그 다음으로 넘어간다.

 

이를 현재노드의 다음노드가 null이 아닐때까지 계속한다.

 

 

 

코드

C++

/**
 * 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 {
private:
    int gcd(int a, int b) {
        if(a%b == 0) return b;
        return gcd(b, a%b);
    }
public:
    ListNode* insertGreatestCommonDivisors(ListNode* head) {
        auto left = head;
        auto right = head -> next;

        while(right != NULL) {
            ListNode* newNode = new ListNode(gcd(max(left -> val, right -> val), min(left -> val, right -> val)));

            left -> next = newNode;
            newNode -> next = right;
            left = right;
            right = right -> next;
        }

        return head;
    }
};

 

GO

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */

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

func insertGreatestCommonDivisors(head *ListNode) *ListNode {

    current := head
    for current.Next != nil {
        g := gcd(current.Val, current.Next.Val)

        newNode := &ListNode{Val: g}
        newNode.Next = current.Next
        current.Next = newNode
        current = newNode.Next
    }

    return head
}