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.
Example 1:
Input: head = [18,6,10,3]
Output: [18,6,6,2,10,1,3]
Explanation: The 1st diagram denotes the initial linked list and the 2nd diagram denotes the linked list after inserting the new nodes (nodes in blue are the inserted nodes).
- We insert the greatest common divisor of 18 and 6 = 6 between the 1st and the 2nd nodes.
- We insert the greatest common divisor of 6 and 10 = 2 between the 2nd and the 3rd nodes.
- We insert the greatest common divisor of 10 and 3 = 1 between the 3rd and the 4th nodes.
There are no more adjacent nodes, so we return the linked list.
Example 2:
Input: head = [7]
Output: [7]
Explanation: The 1st diagram denotes the initial linked list and the 2nd diagram denotes the linked list after inserting the new nodes.
There are no pairs of adjacent nodes, so we return the initial linked list.
Constraints:
- The number of nodes in the list is in the range [1, 5000].
- 1 <= Node.val <= 1000
1. 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 {
public:
ListNode* insertGreatestCommonDivisors(ListNode* head) {
if(!head || !head->next) return head;
ListNode* curr = head;
while(curr->next){
int num = gcd(curr->val,curr->next->val);
// Make a new node
ListNode* temp = new ListNode(num);
// Connect the nodes
temp->next = curr->next;
curr->next = temp;
curr = temp->next;
}
return head;
}
int gcd(int a, int b){
if(b==0) return a;
return gcd(b,a%b);
}
};
2. C
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
int gcd(int a, int b){
if(b==0) return a;
return gcd(b,a%b);
}
struct ListNode* insertGreatestCommonDivisors(struct ListNode* head){
if(!head || !head->next) return head;
struct ListNode* curr = head;
while(curr->next){
int num = gcd(curr->val,curr->next->val);
struct ListNode* temp = (struct ListNode*)malloc(sizeof(struct ListNode));
temp->val = num;
temp->next = curr->next;
curr->next = temp;
curr = temp->next;
}
return head;
}
3. Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def insertGreatestCommonDivisors(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head or not head.next : return head
def gcd(a,b):
if b==0 : return a
return gcd(b,a%b)
curr = head
while curr.next :
num = gcd(curr.val,curr.next.val)
new_node = ListNode(num,curr.next)
curr.next = new_node
curr = new_node.next
return head
깔끔하게 풀었던 문제~ 얍