leetcode [25] K 个一组翻转链表

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

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

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

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

示例：

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

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

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

说明：

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

tail指针从头遍历，计数k，得到需要翻转链表的头和尾。为了方便新建一个头节点和尾节点，其next指向head。每次需要翻转的链表头部为新建尾节点的下一个。

class Solution:
    def reverse(self, head, end):
        prev, cur, post = None, head, None
        while cur != end:
            post = cur.next
            cur.next = prev
            prev = cur
            cur = post
        return prev, head

    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        if not head or k <= 0: return head
        tail = head
        final_head = ListNode(0)
        final_head.next = head
        final_tail = final_head
        count = 0
        while tail:
            count += 1
            tail = tail.next
            if count == k:
                h, t = self.reverse(final_tail.next, tail)
                final_tail.next = h
                t.next = tail
                final_tail = t
                count = 0
        return final_head.next