杭州企业网站设计好公司b站推广网站2022

NC50 链表中的节点每k个一组翻转

题目：

思路：
这种题目比较习惯现在草稿本涂涂画画链表处理过程。整体思路是赋值新的链表，用游离指针遍历原始链表进行翻转操作，当游离个数等于k时，就将翻转后的链表接到新的链表后，如最后个数不满k，则将原始链表剩余节点接到新的链表后。
游离的过程中，每次将当前游离的头节点赋为最新遍历的节点，同时将前一个节点链接到下一个节点。
这个代码写的过程中有点绕，过程有些bug，写了个打印链表的函数调试了下。

代码

class Solution:def reverseKGroup(self , head: ListNode, k: int) -> ListNode:def printList(h):## 打印链表result = []t = hwhile t:result.append(t.val)t = t.nextprint(result)# write code hereif not head or not head.next or k == 1:return headnewHead = ListNode(head.val) ## 最终输出的头节点newTail = ListNode(head.val) ## 每次翻转完成确定尾节点curHead = ListNode(head.val) ## 当前游离的头节点curNode = curHead ## 当前游离节点curTail = curHeadoriNextNode = head.next ## 原始节点顺序oriCurHead = head ## 记录原始链表中每次遍历的组里的头节点count = 1switchTime = 0 ## 成功翻转的组数while curNode:# print(f'{switchTime}次交换的{count}位')if count < k and oriNextNode:## 可以继续遍历的情况curNode = ListNode(oriNextNode.val) ## 游离原始链表的节点curNode.next = curHead ## 将最新的节点指向当前游离组里的头节点，实现翻转curHead = curNode ## 最新节点为头节点oriNextNode = oriNextNode.next if oriNextNode else None ## 继续遍历原始链表count+=1elif count == k:## 成功翻转的情况count = 1switchTime += 1if switchTime == 1:newHead = curHead ## 第一次翻转，获取翻转后的头节点newTail = curTailelse:newTail.next = curHead ## 除了第一次翻转，其余均用翻转后的尾节点做关联指向下一组节点newTail = curTailcurHead = ListNode(oriNextNode.val) if oriNextNode else None ## 获取下一组的头节点curNode = curHeadcurTail = curHeadoriCurHead = oriNextNode ## 获取下一组的原始头节点oriNextNode = oriNextNode.next if oriNextNode else Noneelif switchTime >= 1:## 无法继续遍历，且有翻转过的情况newTail.next = oriCurHeadreturn newHeadelse:## 一次翻转都未成功的情况return head# printList(newHead)# printList(curHead)# printList(head) return newHead