diff options
-rw-r--r-- | insert_gcd_linked_list.c | 45 | ||||
-rw-r--r-- | insert_gcd_linked_list.py | 46 |
2 files changed, 91 insertions, 0 deletions
diff --git a/insert_gcd_linked_list.c b/insert_gcd_linked_list.c new file mode 100644 index 0000000..c62b5ab --- /dev/null +++ b/insert_gcd_linked_list.c @@ -0,0 +1,45 @@ +// 2807. Insert Greatest Common Divisors in Linked List +#include "leetcode.h" + +/* + * 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. return the linked list after + * insertion. the greatest common divisor of two numbers is the largest positive + * integer that evenly divides both numbers. + */ + +int gcd(int a, int b) { + int i = 2, res = 1; + while (i <= a && i <= b) { + if (!(a % i) && !(b % i)) + res = i; + i++; + } + return res; +} + +struct ListNode *insertGreatestCommonDivisors(struct ListNode *head) { + struct ListNode *ans = head; + while (head && head->next) { + int r = gcd(head->val, head->next->val); + struct ListNode *new = (struct ListNode *)malloc(sizeof(struct ListNode)); + new->val = r; + struct ListNode *tmp = head->next; + head->next = new; + new->next = tmp; + head = new->next; + } + return ans; +} + +int main() { + struct ListNode *head = listnode_create(18); + head->next = listnode_create(6); + head->next->next = listnode_create(10); + head->next->next->next = listnode_create(3); + struct ListNode *igcd = insertGreatestCommonDivisors(head); + listnode_print(igcd); // expect: 18 6 6 2 10 1 3 + listnode_free(head); + listnode_free(igcd); +} diff --git a/insert_gcd_linked_list.py b/insert_gcd_linked_list.py new file mode 100644 index 0000000..d737800 --- /dev/null +++ b/insert_gcd_linked_list.py @@ -0,0 +1,46 @@ +# 2807. Insert Greatest Common Divisors in Linked List + +""" +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. return the linked list after +insertion. the greatest common divisor of two numbers is the largest positive +integer that evenly divides both numbers. +""" + + +# Definition for singly-linked list. +class ListNode(object): + def __init__(self, val=0, next=None): + self.val = val + self.next = next + + +class Solution(object): + def gcd(self, a, b): + while b: + a, b = b, a % b + return a + + def insertGreatestCommonDivisors(self, head): + """ + :type head: Optional[ListNode] + :rtype: Optional[ListNode] + """ + if not head or not head.next: + return head + node1 = head + while node1.next: + node2 = node1.next + r = self.gcd(node1.val, node2.val) + new = ListNode(r) + node1.next = new + new.next = node2 + node1 = node2 + return head + + +if __name__ == "__main__": + obj = Solution() + print(obj.insertGreatestCommonDivisors(head=[18, 6, 10, 3])) + print(obj.insertGreatestCommonDivisors(head=[7])) |