leetcode 25 K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例 :

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

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

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

说明 :

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

---

• 非递归

  # Definition for singly-linked list.
  # class ListNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.next = None
  
  class Solution(object):
      def reverseKGroup(self, head, k):
          """
          :type head: ListNode
          :type k: int
          :rtype: ListNode
          """
          dump = ListNode(-1)
          prev = dump # 上一次的尾巴
          prev.next = head
          tail = prev # 从上一次的尾巴开始计数
          while True:
              count = k
              while tail and count:
                  tail = tail.next
                  count -= 1
              if not tail:
                  break
              curr = prev.next
              tag = curr
              while curr is not tail:
                  curr.next, tail.next, prev.next = tail.next, curr, curr.next
                  curr = prev.next
              prev = tag
              tail = tag
          return dump.next

• 递归

  # Definition for singly-linked list.
  # class ListNode(object):
  #     def __init__(self, x):
  #         self.val = x
  #         self.next = None
  
  class Solution(object):
      def reverseKGroup(self, head, k):
          """
          :type head: ListNode
          :type k: int
          :rtype: ListNode
          """
          n = k
          p = head
          tail = None
          while p and n:
              tail = p
              p = p.next
              n -= 1
          if n != 0:
              return head
          tail.next = self.reverseKGroup(tail.next, k)
          while head is not tail:
              p = head
              head = head.next
              p.next = tail.next
              tail.next = p
          return tail