25. k个一组翻转链表

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/

解法一：

用指针对i，j表示要反转的链表首尾，并记录i的前驱pre，写一个辅助函数将i，j范围内的链反转，并保持该段的前驱和后继关系不变。每次j走k步向前探测，若[i:j]段不为空，则调用函数反转。

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        Head = ListNode(0)
        Head.next = head
        if k == 1:
            return head
        pre = j = Head
        i = head
        while j:
            steps = 0
            while j and steps < k:  # j走k步
                j = j.next
                steps += 1
            if j and steps == k:  # 保证j走了k步
                j = self.reverse(pre, i, j, k)    #调用反转，并恢复j指向新链末尾
                pre = j     #更新pre
                i = pre.next    #更新i
        return Head.next
        
    # 反转begin到end的k个结点，并返回反转后的最后一个结点
    def reverse(self, pre, begin, end, k):  
        work = begin.next  # 从begin之后开始
        begin.next = end.next    #保持该段后继
        for _ in range(k - 1):  # 头插法（保持该段前驱为pre）
            tmp = work
            work = work.next
            tmp.next = pre.next
            pre.next = tmp
        return begin  # 反转后最后一个即是begin

2020.3.27

class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        Head = ListNode(0)
        Head.next = head
        start_pre, start, end = Head, head, Head
        count = 0
        #end先走k步，看是否到头
        while end and count < k:
            end = end.next
            count += 1
        #每次循环处理[start, end]部分链表
        while end and count % k == 0:
            start.next = end.next        
            tmp = None        
            for _ in range(k-1):
                tmp = work
                work = work.next
                tmp.next = start_pre.next
                start_pre.next = tmp
            end = start
            start_pre = start
            start = work
            count = 0
            while end and count < k:
                end = end.next
                count += 1
        return Head.next