diff options
Diffstat (limited to 'insert_gcd_linked_list.py')
-rw-r--r-- | insert_gcd_linked_list.py | 46 |
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])) |