K个一组翻转链表

本题出处LeetCode 25题，难度为困难。

• 问题

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

  示例：

  给定这个链表：1->2->3->4->5
  
  当 k = 2 时，应当返回: 2->1->4->3->5
  
  当 k = 3 时，应当返回: 3->2->1->4->5
  
  说明:
  
  你的算法只能使用常数的额外空间。
  你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
  

• 解法

  本题用递归和循环都可以解，用递归写起来比较方便。 主要思想是将链表分为K个一组，从最后一组开始，每一组内进行翻转，返回翻转后的头部节点，将前一组的节点依次连接到后一组的头部。时间复杂度为O(N)，空间复杂度为O(1)。

  class Solution:
  	def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
  		if k == 1:
  			return head
  		cur = head
  		cnt = 0
  		while cur and cnt != k:
  			cur = cur.next
  			cnt += 1
  		if cnt != k:
  			return head
  		nxt = self.reverseKGroup(cur, k)
  		while cnt > 0:
  			new_head = self.move_head(head, nxt)
  			nxt = head
  			head = new_head
  			cnt -= 1
  		return nxt
  
  	def move_head(self, left_head, right_head):
  		"""
  		return: new left head
  		"""
  		tmp = left_head.next
  		left_head.next = right_head
  		return tmp
  

  �行用时 :44 ms, 在所有 python3 提交中击败了99.11% 的用户
  �存消耗 :13.4 MB, 在所有 python3 提交中击败了100.00%的用户