Leetcode 025 K个一组翻转链表 思路详解+反思易错 Python实现_python 反转链表原理

思路：与两两交换节点其实挺类似，只不过现在变成K个一组一起交换。我定义了一个反转K个的函数reverse。这道题最难突破的在于如何K个一起翻转并且将第一次翻转和后面的翻转连续起来。K个一起翻转我利用了不断更新oldhead, newhead的方式，t 始终不动。如何把前后翻转连接？我reverse函数把最新的reverse区间的head return, 改变上一个reverse结尾的next，从而实现连接。

beat 91

class Solution:
    def reverseKGroup(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        #保存头部节点
        t = head
        tot = 0
        p = t
        if k == 1:
            return head
        #用tot算出总节点数，知道什么时候该停止
        while p != None:
            p = p.next
            tot += 1
        #cnt表示目前为止一共reverse了几个节点
        cnt = 0
        #从头部开始遍历
        while t != None:
            #判断翻转K个是否越界
            if cnt + k <= tot:
                #分情况讨论，如果是第一次reverse
                if cnt == 0:
                    head = self.reverse(t, k)
                    cnt += k
                else:
                    #如果不是第一次了
                    #这里有个巧妙的地方，当我们进行完第一次后，t指向第一个reverse区间的最后一个节点
                    i = t.next
                    
                    #通过函数传递一个newhead,用newhead才能改变t.next的值
                    newhead = self.reverse(i, k)
                    #翻转了K个，数量增加K个
                    cnt += k
                    #上个节点的尾部的下一个指向新头
                    t.next = newhead
                    #让t前进，i同样与一开始t一样指向reverse部分最后一个.
                    t = i
            #越界就说明我们已经reverse了能reverse的部分，直接退出
            else:
                break
        return head
                
                
 
    def reverse(self, t, k):
        #记录目前reverse的数量
        count = 1
 
        oldhead = t
        while count < k:
            #每次循环都定义一个新头，这个newhead是t 的下一项。
            newhead = t.next
            #把新头从t的下一项删去
            t.next = newhead.next
            #让新头在t的前面
            newhead.next = oldhead
            #新头变成旧头
            oldhead = newhead
            count += 1
        #返回reverse完后最新的头
        return newhead

反思易错：翻转类题目第一次翻转与接下来的翻转要分开讨论。