# Review list 3

`"""# Definition for a Node.class Node:    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):        self.val = val        self.left = left        self.right = right        self.next = next"""class Solution:    def connect(self, root: 'Node') -> 'Node':        if root is None:return root        nodes = collections.defaultdict(list)        def bfs(node, layer):            from collections import deque            Q = deque([(node,layer)])            while Q:                node, layer = Q.popleft()                nodes[layer].append(node)                if node.left:Q.append((node.left, layer+1))                if node.right:Q.append((node.right, layer+1))        bfs(root, 0)        for l in nodes:            for i in range(len(nodes[l])-1):                nodes[l][i].next = nodes[l][i+1]        return root`
`class Solution:    def connect(self, root: 'Node') -> 'Node':        upper_tail = root        while upper_tail:            dummy_head = Node(-1)            this_tail = dummy_head            while upper_tail:                if upper_tail.left:                    this_tail.next = upper_tail.left                    this_tail = upper_tail.left                if upper_tail.right:                    this_tail.next = upper_tail.right                    this_tail = upper_tail.right                upper_tail = upper_tail.next            upper_tail = dummy_head.next        return root`
`# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    def oddEvenList(self, head: ListNode) -> ListNode:        dummy1 = odd = ListNode(-1)        dummy2 = even = ListNode(-1)        tail = head        while tail:            odd.next = tail            even.next =tail.next            odd = odd.next            even = even.next            if even:                tail = even.next            else:break        odd.next = dummy2.next        return dummy1.next`
`class Solution:    def findClosestElements(self, arr: List[int], k: int, x: int) -> List[int]:        i = bisect.bisect_left(arr, x)        used = 0        res =collections.deque([])        if k>=len(arr):return arr        l, r = i-1, i        while True:            if l>=0 and r<len(arr):                if abs(arr[l]-x)<=abs(arr[r]-x):                    res.appendleft(arr[l])                    l -= 1                    used += 1                else:                    res.append(arr[r])                    r += 1                    used += 1                if used ==k:break            elif l>=0:                res.appendleft(arr[l])                used += 1                l -= 1                if used ==k:break            else:                res.append(arr[r])                used += 1                r += 1                if used ==k:break        return list(res)`
`class Solution:    def firstMissingPositive(self, nums: List[int]) -> int:        nums = [num for num in nums if num>0]        nums = sorted(set(nums))        if not nums:return 1        if nums[0]!=1:return 1        def good(m):return nums[m]==m+1        l, r= 0, len(nums)-1        while l<r:            m = (l+r+1)//2            if good(m):l=m            else:r =m-1        return l+1+1`
`class Solution:    def firstMissingPositive(self, nums: List[int]) -> int:        nums.append(0)        n = len(nums)        for i in range(len(nums)): #delete those useless elements            if nums[i]<0 or nums[i]>=n:                nums[i]=0        for i in range(len(nums)): #use the index as the hash to record the frequency of each number            #print(nums[i])            nums[nums[i]%n]+=n        for i in range(1,len(nums)):            if nums[i]//n==0:                return i        return n`
`"""# Definition for a Node.class Node:    def __init__(self, val=None, next=None):        self.val = val        self.next = next"""class Solution:    def insert(self, head: 'Node', insertVal: int) -> 'Node':        if head is None:            new_head = Node(insertVal)            new_head.next = new_head            return new_head        min_node = tail = head        max_node = head        tail = head.next        while tail!=head:            if tail.val<min_node.val:                min_node = tail            elif tail.val>=max_node.val:                max_node = tail            tail = tail.next        new_node = Node(insertVal)       # print(min_node.val, max_node.val)        if max_node.val<=insertVal or min_node.val>=insertVal:            max_node.next = new_node            new_node.next = min_node            return head        tail = min_node        while True:            #print(tail.val)            if tail.next.val>=insertVal:                nxt = tail.next                tail.next = new_node                new_node.next = nxt                break            tail = tail.next        return head`

--

--

## More from Jimmy (xiaoke) Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.