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]))
|