链表

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

92反转链表2

pre:开始反转的前一个节点

cur:原链表当前节点

ne:原链表下一个节点

nx:新链表下一个节点,初始化为第n+1个节点

class Solution:
    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
        tmp = ListNode(0)
        tmp.next = head
        pre = tmp
        cur = tmp
        
        
        for i in range(m):
            pre = cur
            cur = cur.next
        p = cur
        for i in range(n-m+1):
            p = p.next
        nx = p#这里的nx是更新后的nx 1→2→3→4→5中更新后4→3→2→5  那么第一次到2时 更新后2→5 nx初始化为5 cur=ne=3后nx=2 
        while cur!=p:# a b c
            ne = cur.next
            # print(pre.val,cur.val,ne.val)
            cur.next = nx
            nx = cur
            cur = ne
            
        pre.next = nx# fro:1→2→3→4→5中的1
        return tmp.next

链表排序

147链表插入排序O(n^2)

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        tmp = ListNode(0)
        tmp.next = head
        pre = tmp
        cur = head
        while cur:
            ne = cur.next
            p = tmp.next
            pre = tmp
            if not ne:
                break
            if ne.val<cur.val:
                nee = ne.next
                ne.next = None
                while p.next!=ne and p.val<ne.val:
                    p = p.next
                    pre = pre.next
                cur.next = nee#把ne删了
                pre.next = ne
                ne.next = p
            else:
                cur = cur.next
                continue
            if cur.next and cur.next.val>cur.val:
                cur = cur.next
        return tmp.next

148链表归并排序O(nlog(n))

class Solution:
    def sortList(self, head: ListNode) -> ListNode:
        def dfs(p):
            if not p or not p.next:
                return p
            s,f = p,p.next
            while f and f.next:
                s,f = s.next,f.next.next
            # 截断
            mid,s.next = s.next,None
            # 先把子序列排好
            l,r = dfs(p),dfs(mid)
            h = res = ListNode(0)
            while l and r:
                if l.val<r.val:
                    h.next = l
                    l = l.next
                else:
                    h.next = r
                    r = r.next
                h = h.next
            h.next = l if l else r
            return res.next
        return dfs(head)