当前位置： 移动技术网 > IT编程>脚本编程>Python > Leetcode刷题记录——25. K 个一组翻转链表

Leetcode刷题记录——25. K 个一组翻转链表

2020年07月20日  | 移动技术网IT编程  | 我要评论

在这里插入图片描述
在这里插入图片描述

步骤
主函数思路：
不断地调用另一个递归函数
每次调用的递归函数可以将当前节点开始到第k个节点的区段反转，并记录当前区段后面的下一个节点
以便调整下一段区段的时候 有头结点可用

递归函数函数
其输入是起始节点，目前节点对应在本区段的序号以及k
功能是尝试对k个元素进行反转
输出是反转后的新头节点（原本的这一区段的尾节点），下一段的头结点（原本尾结点的next）以及新尾节点（原本这一区段的头节点）
一开始先判断
1、如果起始起点（含）后面不够k个元素(if cnt <= k and root == None:)
则反回三个None
2、如果到了第k个节点（if cnt == k:）
则先记录下一阶段的新头结点next_stage_head = root.next
再记录这个节点作为新的头结点new_head = root
最后返回return root,next_stage_head,new_head
3、如果还没到k且非空
递归到下一个节点
new,next_stage_head,new_head = self.recurse(root.next,cnt+1,k)
这里的返回值中，next_stage_head,new_head是递归到第k个节点时返回的
一层一层往外传出来
3.1如果此时new_head 意味着 这段链表中元素不够k个了 根据示例，不需要反转 则直接返回None 到主函数
3.2new是上一层的节点 也就是正序中自身的下一个节点 因为要反转 需要将这个节点调整为自身的父节点
new.next = root
return root,next_stage_head,new_head

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

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if head == None:
            return None
        faker = ListNode('skt')#从韩国请来一个家伙作为伪头节点
        faker.next = head#伪头结点自然认为是原head的父节点
        last_tail = faker#可以将伪头节点视作上一个反转区段的尾节点
        last_tail,next_stage_head,new_head = self.recurse(head,1,k)
        #第一次调用递归函数 
        #递归函数的输入是 本阶段待反转的原节点（即反转后是本区段的尾节点）
        #第二个输入是 当前节点对应在本区段的序号 从1开始算
        #第三个是k
        if new_head == None:#如果第一次调用即失败 说明原链表长度不够k个 
            return faker.next#直接返回原链表头节点即可
        faker.next = new_head#第一次调用后 伪头节点指新头结点
        while next_stage_head != None:#如果上一次反转成功
            beifen = next_stage_head#留一个备份 如果本次反转失败 则直接以原本的头结点作为上一阶段尾结点的next
            new_tail,next_stage_head,new_head = self.recurse(next_stage_head,1,k)#反转
            if new_head == None:#反转失败
                last_tail.next = beifen#使用备份
                return faker.next
            last_tail.next = new_head#反转成功 记录本阶段反转后的新头结点为上次递归的尾节点的next
            last_tail = new_tail#记录本阶段的新尾节点为下次递归的上阶段尾结点
        last_tail.next = next_stage_head
        return faker.next

    def recurse(self,root,cnt,k):
        if cnt <= k and root == None:#还没到第k个 即为None 反转失败
            return None,None,None#返回三个None
        if cnt == k:#到了第k个 反转成功
            next_stage_head = root.next#将这个节点的下一个作为下一阶段的头结点
            new_head = root#将这个节点作为本阶段的新头结点
            return root,next_stage_head,new_head#返回当前节点 下一阶段的头结点和新头结点 其中后两个一层层传出去，在递归完最后一层后 往外传递时不改变
        else:#还没到最后一层 也不是空
            new,next_stage_head,new_head = self.recurse(root.next,cnt+1,k)#先递归下一层
            if new_head == None:#看看递归结果是否成功 不成功即返回3个None
                return None,None,None
            new.next = root#成功 将原来自己的next  改为自己的父节点
            return root,next_stage_head,new_head#返回三个节点

本文地址：https://blog.csdn.net/weixin_41545780/article/details/107437760

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网