insert_greatest_common_divisors_in_linked_list
1from utils import ListNode 2from typing import Optional 3 4# @leet start 5from math import gcd 6 7 8class Solution: 9 def insertGreatestCommonDivisors( 10 self, head: Optional[ListNode] 11 ) -> Optional[ListNode]: 12 """ 13 This question asks us to insert the gcd of pairs of items in between nodes 14 We can do this by having a slow pointer and fast pointer that are 15 next to each other. We then take both their values, calculate their gcd, 16 and insert a new node in between them. 17 So, imagine this list: 18 19 18 -> 6 -> 3 20 We would want to insert 6 and 3 in between: 21 18 -> 6 -> 6 -> 3 -> 3 22 So we set up a fast and slow pointer: 23 18 -> 6 24 ^ ^ 25 And then we take both their values, calculate their gcd and create a new node. 26 We then set slow.next to the new node, and then connect the new node 27 to the fast node. Finally, we set slow equal to fast (to jump over the 28 new node) and increment the fast pointer. 29 30 At the end we return our copy of the head node. 31 """ 32 if not head: 33 return None 34 dummy = slow = fast = head 35 fast = fast.next 36 37 while slow and fast: 38 gcd_node = ListNode(gcd(fast.val, slow.val)) 39 slow.next = gcd_node 40 gcd_node.next = fast 41 slow = fast 42 fast = fast.next 43 return dummy 44 45 46# @leet end 47 48 49def test(): 50 assert 2 + 2 == 4
class
Solution:
9class Solution: 10 def insertGreatestCommonDivisors( 11 self, head: Optional[ListNode] 12 ) -> Optional[ListNode]: 13 """ 14 This question asks us to insert the gcd of pairs of items in between nodes 15 We can do this by having a slow pointer and fast pointer that are 16 next to each other. We then take both their values, calculate their gcd, 17 and insert a new node in between them. 18 So, imagine this list: 19 20 18 -> 6 -> 3 21 We would want to insert 6 and 3 in between: 22 18 -> 6 -> 6 -> 3 -> 3 23 So we set up a fast and slow pointer: 24 18 -> 6 25 ^ ^ 26 And then we take both their values, calculate their gcd and create a new node. 27 We then set slow.next to the new node, and then connect the new node 28 to the fast node. Finally, we set slow equal to fast (to jump over the 29 new node) and increment the fast pointer. 30 31 At the end we return our copy of the head node. 32 """ 33 if not head: 34 return None 35 dummy = slow = fast = head 36 fast = fast.next 37 38 while slow and fast: 39 gcd_node = ListNode(gcd(fast.val, slow.val)) 40 slow.next = gcd_node 41 gcd_node.next = fast 42 slow = fast 43 fast = fast.next 44 return dummy
10 def insertGreatestCommonDivisors( 11 self, head: Optional[ListNode] 12 ) -> Optional[ListNode]: 13 """ 14 This question asks us to insert the gcd of pairs of items in between nodes 15 We can do this by having a slow pointer and fast pointer that are 16 next to each other. We then take both their values, calculate their gcd, 17 and insert a new node in between them. 18 So, imagine this list: 19 20 18 -> 6 -> 3 21 We would want to insert 6 and 3 in between: 22 18 -> 6 -> 6 -> 3 -> 3 23 So we set up a fast and slow pointer: 24 18 -> 6 25 ^ ^ 26 And then we take both their values, calculate their gcd and create a new node. 27 We then set slow.next to the new node, and then connect the new node 28 to the fast node. Finally, we set slow equal to fast (to jump over the 29 new node) and increment the fast pointer. 30 31 At the end we return our copy of the head node. 32 """ 33 if not head: 34 return None 35 dummy = slow = fast = head 36 fast = fast.next 37 38 while slow and fast: 39 gcd_node = ListNode(gcd(fast.val, slow.val)) 40 slow.next = gcd_node 41 gcd_node.next = fast 42 slow = fast 43 fast = fast.next 44 return dummy
This question asks us to insert the gcd of pairs of items in between nodes We can do this by having a slow pointer and fast pointer that are next to each other. We then take both their values, calculate their gcd, and insert a new node in between them. So, imagine this list:
18 -> 6 -> 3 We would want to insert 6 and 3 in between: 18 -> 6 -> 6 -> 3 -> 3 So we set up a fast and slow pointer: 18 -> 6 ^ ^ And then we take both their values, calculate their gcd and create a new node. We then set slow.next to the new node, and then connect the new node to the fast node. Finally, we set slow equal to fast (to jump over the new node) and increment the fast pointer.
At the end we return our copy of the head node.
def
test():