NC50 链表中的节点每k个一组翻转
题目:
思路:
这种题目比较习惯现在草稿本涂涂画画链表处理过程。整体思路是赋值新的链表,用游离指针遍历原始链表进行翻转操作,当游离个数等于k时,就将翻转后的链表接到新的链表后,如最后个数不满k,则将原始链表剩余节点接到新的链表后。
游离的过程中,每次将当前游离的头节点赋为最新遍历的节点,同时将前一个节点链接到下一个节点。
这个代码写的过程中有点绕,过程有些bug,写了个打印链表的函数调试了下。
代码
class Solution:
def reverseKGroup(self , head: ListNode, k: int) -> ListNode:
def printList(h):
## 打印链表
result = []
t = h
while t:
result.append(t.val)
t = t.next
print(result)
# write code here
if not head or not head.next or k == 1:
return head
newHead = ListNode(head.val) ## 最终输出的头节点
newTail = ListNode(head.val) ## 每次翻转完成确定尾节点
curHead = ListNode(head.val) ## 当前游离的头节点
curNode = curHead ## 当前游离节点
curTail = curHead
oriNextNode = head.next ## 原始节点顺序
oriCurHead = head ## 记录原始链表中每次遍历的组里的头节点
count = 1
switchTime = 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+=1
elif count == k:
## 成功翻转的情况
count = 1
switchTime += 1
if switchTime == 1:
newHead = curHead ## 第一次翻转,获取翻转后的头节点
newTail = curTail
else:
newTail.next = curHead ## 除了第一次翻转,其余均用翻转后的尾节点做关联指向下一组节点
newTail = curTail
curHead = ListNode(oriNextNode.val) if oriNextNode else None ## 获取下一组的头节点
curNode = curHead
curTail = curHead
oriCurHead = oriNextNode ## 获取下一组的原始头节点
oriNextNode = oriNextNode.next if oriNextNode else None
elif switchTime >= 1:
## 无法继续遍历,且有翻转过的情况
newTail.next = oriCurHead
return newHead
else:
## 一次翻转都未成功的情况
return head
# printList(newHead)
# printList(curHead)
# printList(head)
return newHead