aboutsummaryrefslogtreecommitdiff
path: root/insert_gcd_linked_list.py
blob: d737800beedd4e9e5c278aa496ea51fdb7aec891 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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]))