我胡汉三又回来了 ！！！141 - 148

唉  人总是幻想以后的自己会更好  ，实际上 你现在是什么样 大概率你后面就是什么样子 。 我总是想年后一定全新学习，天天早睡早起，锻炼身体，可是过完年依然得过且过，blabla。定目标 就要定当下的目标！！！

不过至少过年的时候力扣没落下  

141 环形链表 。

 是否有环 快慢指针 经典 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head == None:
            return False
        q = s = head
        while q.next != None:
            q = q.next
            s = s.next
            if q.next:
                q = q.next
            else:
                return False
            if q == s:
                return True
        return False

作者：yizhu-jia
链接：https://leetcode-cn.com/problems/linked-list-cycle/solution/yi-kuai-da-man-gong-qi-bu-bei-by-yizhu-j-howw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

142   找环入口 这也算经典题目了 

但是我一直不会 数学问题真的都好难 

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: ListNode) -> ListNode:
        if head == None:
            return None
        q = s = head
        while q.next != None:
            q = q.next
            s = s.next
            if q.next:
                q = q.next
            else:
                return None
            if q == s:
                s = head
                while  q != s:
                    q = q.next 
                    s = s.next
                return q
        return None

作者：yizhu-jia
链接：https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/shuang-zhi-zhen-a-shuang-zhi-zhen-yi-yu-4w15e/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

143 重排链表 

思路就是 找到后一半  然后后一半反向 再把两段拼起来。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head :
            return head
        n = 0
        p = head
        while p != None:
            n += 1
            p = p.next
        i = 1
        p = q = head
        while i < (n+1)//2:         #将q指向后半段开头的前一个
            q = q.next
            i += 1
        #将后半段反向
        r = q.next
        q.next = None
        while r != None:
            temp = r.next
            r.next = q.next
            q.next = r
            r = temp
        temp = q
        q = q.next
        temp.next = None
    #将两段拼起来：
        r = p
        p = p.next
        while p != None:
            r.next = q
            r = r.next
            q = q.next
            r.next = p
            r = r.next
            p = p.next
        if q :
            r.next = q
        return head

作者：yizhu-jia
链接：https://leetcode-cn.com/problems/reorder-list/solution/bei-jue-da-duo-shu-ren-ji-bai-by-yizhu-j-8y6m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

144：

二叉树的前序遍历  

简简单单的递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        rel = []
        def preorder(root):
            rel.append(root.val)
            if root.left:
                preorder(root.left)
            if root.right:
                preorder(root.right)
        if root:
            preorder(root)
        return rel


作者：yizhu-jia
链接：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/solution/jian-dan-de-di-gui-bu-jian-dan-de-yi-tia-6rvl/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

145：

后序 简单的递归

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        rel = []
        def postorder(root):
            if root.left:
                postorder(root.left)
            if root.right:
                postorder(root.right)
            rel .append(root.val)

        if root :
            postorder(root)
        return rel

作者：yizhu-jia
链接：https://leetcode-cn.com/problems/binary-tree-postorder-traversal/solution/wei-shi-yao-zhe-shi-wei-shi-yao-by-yizhu-l6av/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 146：LRU 不多说 有点好玩 

class LRUCache:

    def __init__(self, capacity: int):
        self.dict1 = {}
        self.room = capacity
        self.left = linknode(-1,-1)
        self.right = linknode(-1,-1,pri=self.left)
        self.left.next = self.right
    def addlink(self,pri,next,mid):
        pri.next = mid
        next.pri = mid
        mid.next = next
        mid.pri = pri
    def dellink(self,  mid):
        mid.pri.next = mid.next
        mid.next.pri = mid.pri
    def move2right(self,mid):
        self.dellink(mid)
        self.addlink(self.right.pri,self.right,mid)
    def get(self, key: int) -> int:
        if key in self.dict1:
            self.move2right(self.dict1[key])
            return self.dict1[key].value
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key not in self.dict1:

            # if len(self.dict1) == 0:        #如果是第一个节点  那么就变成l - KEY - r这样的结构
            #     self.addlink(self.left,self.right,self.dict1[key])
            # elif len(self.dict1) == self.room:
            if len(self.dict1) == self.room:    #如果满了 就删除最左边这个结点 ，把新结点挂在最右边
                self.dict1[key] = linknode(key, value)
                del self.dict1[self.left.next.key]
                self.dellink(self.left.next)
                self.addlink(self.right.pri,self.right,self.dict1[key])
            else:             #如果没满  就单纯的挂在右边就好。
                self.dict1[key] = linknode(key, value)
                self.addlink(self.right.pri, self.right, self.dict1[key])
        else:       #如果已经存在  修改键值  并放在最后
            self.dict1[key].value = value
            self.move2right(self.dict1[key])

class linknode:
    def __init__(self, key=-1,value=0, pri=None,next=None):
        self.key = key
        self.value = value
        self.next = next
        self.pri = pri


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

class LRUCache:

    def __init__(self, capacity: int):
        self.dict1 = {}
        self.room = capacity
        self.left = linknode(-1,-1)
        self.right = linknode(-1,-1,pri=self.left)
        self.left.next = self.right
    def addlink(self,pri,next,mid):
        pri.next = mid
        next.pri = mid
        mid.next = next
        mid.pri = pri
    def dellink(self,  mid):
        mid.pri.next = mid.next
        mid.next.pri = mid.pri
    def move2right(self,mid):
        self.dellink(mid)
        self.addlink(self.right.pri,self.right,mid)
    def get(self, key: int) -> int:
        if key in self.dict1:
            self.move2right(self.dict1[key])
            return self.dict1[key].value
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key not in self.dict1:

            # if len(self.dict1) == 0:        #如果是第一个节点  那么就变成l - KEY - r这样的结构
            #     self.addlink(self.left,self.right,self.dict1[key])
            # elif len(self.dict1) == self.room:
            if len(self.dict1) == self.room:    #如果满了 就删除最左边这个结点 ，把新结点挂在最右边
                self.dict1[key] = linknode(key, value)
                del self.dict1[self.left.next.key]
                self.dellink(self.left.next)
                self.addlink(self.right.pri,self.right,self.dict1[key])
            else:             #如果没满  就单纯的挂在右边就好。
                self.dict1[key] = linknode(key, value)
                self.addlink(self.right.pri, self.right, self.dict1[key])
        else:       #如果已经存在  修改键值  并放在最后
            self.dict1[key].value = value
            self.move2right(self.dict1[key])

class linknode:
    def __init__(self, key=-1,value=0, pri=None,next=None):
        self.key = key
        self.value = value
        self.next = next
        self.pri = pri


# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

147：

对链表插入排序 

简单题 但是得好好想想边界条件

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        if not head:
            return head
        post = ListNode(val = -1,next=head)
        p = head.next
        r = head
        r.next = None
        while p != None:
            temp = post
            while p.val > temp.next.val:
                temp = temp.next          #找到P插入的位置
                if temp.next == None:
                    break
            q = p.next          #記錄p的下一个
            p.next = temp.next
            temp.next = p
            p = q
        return post.next

作者：yizhu-jia
链接：https://leetcode-cn.com/problems/insertion-sort-list/solution/zen-yao-zhe-yao-duo-ren-ji-bai-wo-by-yiz-bfvu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

148 排序链表  

我太懒了  所以我直接化身CV工程师 

# 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]:
        def merge(head1: ListNode, head2: ListNode) -> ListNode:
            dummyHead = ListNode(0)
            temp, temp1, temp2 = dummyHead, head1, head2
            while temp1 and temp2:
                if temp1.val <= temp2.val:
                    temp.next = temp1
                    temp1 = temp1.next
                else:
                    temp.next = temp2
                    temp2 = temp2.next
                temp = temp.next
            if temp1:
                temp.next = temp1
            elif temp2:
                temp.next = temp2
            return dummyHead.next
        
        if not head:
            return head
        
        length = 0
        node = head
        while node:
            length += 1
            node = node.next
        
        dummyHead = ListNode(0, head)
        subLength = 1
        while subLength < length:
            prev, curr = dummyHead, dummyHead.next
            while curr:
                head1 = curr
                for i in range(1, subLength):
                    if curr.next:
                        curr = curr.next
                    else:
                        break
                head2 = curr.next
                curr.next = None
                curr = head2
                for i in range(1, subLength):
                    if curr and curr.next:
                        curr = curr.next
                    else:
                        break
                
                succ = None
                if curr:
                    succ = curr.next
                    curr.next = None
                
                merged = merge(head1, head2)
                prev.next = merged
                while prev.next:
                    prev = prev.next
                curr = succ
            subLength <<= 1
        
        return dummyHead.next



作者：yizhu-jia
链接：https://leetcode-cn.com/problems/sort-list/solution/wo-hao-lan-zhen-de-by-yizhu-jia-line/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。