aboutsummaryrefslogtreecommitdiff
path: root/insert_gcd_linked_list.py
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-09-09 22:04:24 -0600
committerJack Sangdahl <[email protected]>2024-09-09 22:04:24 -0600
commit628024d350e3769cb86aaadc1043d9aaf452de3c (patch)
treef80c5139bd785ff3ee36c544a42168d252ddbb32 /insert_gcd_linked_list.py
parentc52e6aefdc74847dff8ac39dd89b5253b375f524 (diff)
downloadleetcode-628024d350e3769cb86aaadc1043d9aaf452de3c.tar.gz
leetcode-628024d350e3769cb86aaadc1043d9aaf452de3c.zip
2807. insert greatest common divisor in linked list
Diffstat (limited to 'insert_gcd_linked_list.py')
-rw-r--r--insert_gcd_linked_list.py46
1 files changed, 46 insertions, 0 deletions
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]))