唉  人总是幻想以后的自己会更好  ，实际上 你现在是什么样 大概率你后面就是什么样子 。 我总是想年后一定全新学习，天天早睡早起，锻炼身体，可是过完年依然得过且过，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：

对链表插入排序 

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

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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 

147 排序链表  

我太懒了  所以我直接化身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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。