aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--insert_gcd_linked_list.c45
-rw-r--r--insert_gcd_linked_list.py46
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]))