leetcode

commit 628024d350e3769cb86aaadc1043d9aaf452de3c
parent c52e6aefdc74847dff8ac39dd89b5253b375f524
Author: Jack Sangdahl <jack@pngu.org>
Date:   Mon,  9 Sep 2024 22:04:24 -0600

2807. insert greatest common divisor in linked list

Diffstat:
A
insert_gcd_linked_list.c
 | 
45
+++++++++++++++++++++++++++++++++++++++++++++
A
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
@@ -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
@@ -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]))