首页 > 代码库 > leetcode 【 Reverse Nodes in k-Group 】 python 实现
leetcode 【 Reverse Nodes in k-Group 】 python 实现
原题：
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
代码：oj测试通过 Runtime: 125 ms
1 # Definition for singly-linked list. 2 # class ListNode: 3 # def __init__(self, x): 4 # self.val = x 5 # self.next = None 6 7 class Solution: 8 # @param head, a ListNode 9 # @param k, an integer10 # @return a ListNode11 def reverseKGroup(self, head, k):12 if head is None or head.next is None or k<2:13 return head14 15 dummyhead = ListNode(0)16 dummyhead.next = head17 18 slow = dummyhead19 fast = dummyhead20 21 while 1:22 sign = 023 for i in range(k):24 if fast.next is not None:25 fast = fast.next26 else:27 sign = 128 break29 if sign == 1 :30 break31 else:32 curr = slow.next33 for i in range(k-1):34 tmp = curr.next35 curr.next = tmp.next36 tmp.next = slow.next37 slow.next = tmp38 slow = curr39 fast = curr40 41 return dummyhead.next
思路：
这道题看主要有两个点：
1. 快慢指针技巧：fast指针在前面探路，如果不满足翻转的条件，退出直接返回；slow指针在后面跟着，slow.next始终指向待翻转的第一个ListNode位置
2. 链表翻转：这个我在之前的一篇日志中已经说明了，用了一个书本倒叙的例子，详情见http://www.cnblogs.com/xbf9xbf/p/4212159.html这篇日志。
总的思路就是把看似复杂的任务分解成小任务，然后逐个击破。
leetcode 【 Reverse Nodes in k-Group 】 python 实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。