# Week3 - Sorting

###### tags: `Leetcode`

## 56. Merge Intervals

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        res = []
        intervals.sort(key=lambda x: x[0])
        left, right = intervals[0]
        
        for interval in intervals: 
            if interval[0] > right:
                res.append([left, right])
                left, right = interval
                
            elif interval[1] > right:
                right = interval[1]    
                    
        res.append([left, right])
        return res

## 75. Sort Colors

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        nums.sort()

## 88. Merge Sorted Array

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        temp = nums1[:m]
        i, j, k = 0, 0, 0
        
        while i < m and j < n:
            if temp[i] > nums2[j]: 
                nums1[k] = nums2[j]
                j += 1
                k += 1
                
            else: 
                nums1[k] = temp[i]
                i += 1
                k += 1 
        
        while i < m:
            nums1[k] = temp[i]
            i += 1
            k += 1
            
        while j < n: 
            nums1[k] = nums2[j]
            j += 1
            k += 1

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        p1 = m+n-1
        # Reverse order
        while m > 0 and n > 0:
            if nums1[m-1] > nums2[n-1]:
                nums1[p1] = nums1[m-1]
                m -= 1
            else:
                nums1[p1] = nums2[n-1]
                n -= 1
            p1 -= 1
        # Edge case: fill nums1 with leftover nums2 elements
        while n > 0:
            nums1[p1] = nums2[n-1]
            p1, n = p1-1, n-1

## 49. Group Anagrams

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = defaultdict(list)
        for s in strs:
            dic[''.join(sorted(s))].append(s)
        return dic.values()

## 148. Sort List

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        a_list = [] 
        origin = head
        
        while head is not None:  
            a_list.append(head.val)
            head = head.next
            
        a_list.sort()
        head = origin 
        
        for ele in a_list:
            head.val = ele
            head = head.next 
        return origin 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        
        # split the list into two halfs:
        left = head
        right = self.getMid(head)
        tmp = right.next
        right.next = None
        right = tmp
        
        left = self.sortList(left) 
        right = self.sortList(right) 
        return self.merge(left, right)
        
    def getMid(self,head):
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return  slow
    
    def merge(self, left, right):
        tail = dummy = ListNode()
        while left and right:
            if left.val < right.val:
                tail.next = left
                left = left.next
            else:
                tail.next = right
                right = right.next
            tail = tail.next
        if left:
            tail.next = left
        if right:
            tail.next = right   
        return dummy.next

## 147. Insertion Sort List

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        root = ListNode(0) 
        root.next = head
        
        while head.next: 
            if head.val <= head.next.val:
                head = head.next
            else: 
                tmp = head.next
                q = root
                head.next = head.next.next
                while True:
                    if q.next.val <= tmp.val:
                        q = q.next
                    else:
                        tmp.next = q.next
                        q.next = tmp 
                        break
        return root.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        dummy = ListNode(0, head)
        prev, cur = head, head.next
        while cur:
            if cur.val >= prev.val:
                prev, cur = cur, cur.next
                continue
            tmp = dummy
            while cur.val > tmp.next.val:
                tmp = tmp.next
            prev.next = cur.next
            cur.next = tmp.next
            tmp.next = cur
            cur = prev.next
        return dummy.next

+ Link
+ https://blog.csdn.net/fuxuemingzhu/article/details/80785630