Python实现k个一组的链表反转

链表反转"/>

Python实现k个一组的链表反转

题目描述

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

LeetCode原题地址：/

测试用例

• 示例

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

代码实现

我们可以将这个问题拆分成两个子问题，首先将链表进行分组，再将分组后的子链表进行反转。关于链表的反转可以参考我的这篇文章Python实现反转链表

需要注意的是：在对子链表进行反转之后，记得要更新节点的指向。

class ListNode:def __init__(self,val,next=None):if isinstance(val,int):self.val = valself.next = nextelif isinstance(val,list):self.val = val[0]self.next = Nonehead = selffor i in range(1,len(val)):node = ListNode(val[i])head.next = nodehead = head.nextclass Solution:def reverseListNode(self,head:ListNode,tail:ListNode):"""反转子链表:param head:链表的头节点:param tail:链表的尾结点:return:反转之后链表的头结点和尾结点"""prev = tail.nextcurrent = headwhile prev != tail:next = current.nextcurrent.next = prevprev = currentcurrent = nextreturn tail,headdef reverseKGroup(self, head: ListNode, k: int) -> ListNode:#创建一个哑结点dummy_head = ListNode(0)dummy_head.next = headprev =dummy_headwhile head:tail = prevfor i in range(k):tail = tail.nextif not tail:return dummy_head.nextnext = tail.next#反转子链表head,tail = self.reverseListNode(head,tail)#更新节点的指向prev.next = headtail.next = next#处理后面的子链表prev = tailhead = tail.nextreturn dummy_head.nextl = [1,2,3,4,5]
list_node = ListNode(l)
obj = Solution()
reve_node = obj.reverseKGroup(list_node,2)
while reve_node:print(reve_node.val)reve_node = reve_node.next

参考：K 个一组翻转链表