欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

K 个一组翻转链表

程序员文章站 2023-11-21 11:47:40
步骤主函数思路:不断地调用另一个递归函数每次调用的递归函数可以将当前节点开始到第k个节点的区段反转,并记录当前区段后面的下一个节点以便调整下一段区段的时候 有头结点可用递归函数函数其输入是起始节点,目前节点对应在本区段的序号以及k功能是尝试对k个元素进行反转输出是反转后的新头节点(原本的这一区段的尾节点),下一段的头结点(原本尾结点的next)以及新尾节点(原本这一区段的头节点)一开始先判断1、如果起始起点(含)后面不够k个元素(if cnt <= k and root == .....

K 个一组翻转链表
K 个一组翻转链表

步骤
主函数思路:
不断地调用另一个递归函数
每次调用的递归函数可以将当前节点开始到第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