aboutsummaryrefslogtreecommitdiff
path: root/insert_gcd_linked_list.c
diff options
context:
space:
mode:
Diffstat (limited to 'insert_gcd_linked_list.c')
-rw-r--r--insert_gcd_linked_list.c45
1 files changed, 45 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);
+}