23.合并k个升序链表
在这里插入图片描述
首先拿到这个问题,其实思路很简单,因为它是升序的,所以你只要比较每个列表的第一个,然后把小的放到最后整合的数组的最后一个就可以了。

class Solution:
    def mergeKLists(self, lists: List[ListNode]) ->ListNode:    #这里的lists记录每一个链表的头结点
        head = ListNode()    #头结点,记录链表的头结点
        p = ListNode()
        head = p
        while(True):
            mIn = 0
            for i in range(0,len(lists)):     #判断是否所有链表都已经被遍历结束   
                if(lists[mIn]==None):
                    mIn+=1
                else:
                    break
            if mIn==len(lists):
                break
            for i in range(1,len(lists)):#找出这些结点里的最小结点
                if(lists[i] == None):
                    continue
                if(lists[mIn].val>lists[i].val):
                    mIn = i
            p.next = lists[mIn]    #把小的放在链表的最后一个
            lists[mIn]= lists[mIn].next    
            p = p.next
        return head.next

24.两两交换链表中的节点
在这里插入图片描述
拿到这题,你要理解你要做的事有哪些,首先,两两结点交换位置,本来1指向2,现在要变成2指向1,且1的前置结点也要指向2,1也要指向2的后置结点。
head->1->2->3
变成
head->2->1->3
思路:用一个指针记录前置结点h,p和q分别指向1和2——当前要交换的节点,
然后,p.next=q.next 先把1指向3
然后,让q指向p 2指向1
最后就是h指向q了
到这里指向问题解决,然后把h指向p就可以进行下一组两个结点的交换了。

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head ==None:
            return head
        h = ListNode()
        p = ListNode()
        q = ListNode()
        h.next = head
        p = head
        if head.next != None:
            head = head.next
        while p!=None and q!=None:
            q = p.next
            if q ==None:
                break
            p.next = q.next
            q.next = p
            h.next = q
            h = p
            p = p.next
        return head

25、接下来这题是上一题的扩展,原本是固定两个链表结点的交换,现在是不固定数量的,且是以某一个对称轴,两两对称结点交换。
在这里插入图片描述
在这里插入图片描述
思路:这道题拿到之后,每一组交换开始,你首先要做的应该是判断这一组数据是否存在,如果不存在就结束,存在就开始交换。
然后再考虑这道题你要做哪些事,前置结点的指向和后置结点的延续交换。
所以这一题我用了4个指针,
在这里插入图片描述
定位了h结点之后,要定位t_h结点。比如这次交换长度为k个,2<=k,比如现在是第一对,说明前面没交换过,那k假设为5,那t_h就是第4个,h就是第一个,那就要往后找3次,1->2->3->4,所以是k-2-count*2,count用来记录已经找了几对了,因为每一对减少两个。
定位完结点后,开始交换,h_h指向t,这里肯定没问题,但是t_h指向h的时候就可能出现问题,因为当这一对结点相邻的时候,t_h就是h,所以要加一个判断,分情况求解。
在这里插入图片描述
如果t_h和h重合的话,t.next就是h,如果不重合,t.next就是h.next。
到这里已经完成了t位置的转换,现在是h,直接换就行。
然后重新定位一下h_h的位置就可以,向后找k/2个链表结点。
在这里插入图片描述

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        if k==1:
            return head
        h_h = ListNode()    #用于记录目前正在交换链表结点对的前置结点的父结点
        h = ListNode()      #用于记录目前正在交换链表结点对的前置结点
        t_h = ListNode()    #用于记录目前正在交换链表结点对的后置结点的父结点
        t = ListNode()      #用于记录目前正在交换链表结点对的后置结点
        temp = ListNode()
        count  = 0  #记录正在交换第几次
        h_h.next = head
        head =h_h
        def ishasgroup(h,k):        #看看是否存在一组数据
            for i in range(0,k):
                h = h.next
                if h==None:
                    return False
                if h.next == None:
                    break


            if i == k-1 and h!=None:
                return True
            else:
                return False
        while(ishasgroup(h_h,k)):
            count =0
            while(count<int(k/2)):
                h = h_h.next
                t_h = h
                for i in range(0,k-2-count*2):
                    t_h = t_h.next
                t = t_h.next        #到这里为止为记录4个指针
                h_h.next = t        
                temp = t.next        #用于记录t的后置结点
                if t_h!=h:
                    t.next = h.next
                else:
                    t.next=h
                t_h.next = h
                h.next = temp
                h_h = h_h.next
                count+=1
            if k%2==1:
                for i in range(0,int(k/2)+1):
                    h_h = h_h.next
            else:
                for i in range(0,int(k/2)):
                    h_h = h_h.next
        return head.next