链表反转"/>
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 个一组翻转链表
更多推荐
Python实现k个一组的链表反转
发布评论