题解 | #链表中的节点每k个一组翻转#

链表中的节点每k个一组翻转

http://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e

这里讲一下递归的解法，因为我们不能确定链表长度，所以我们可以先正向迭代直到尾部，然后再反向递归地进行链表的翻转。

每次转入的都是K个节点中开始的那个节点，然后我们判断这组是不是最后一组，

如果这组是最后一组并且不够K个，那么我们就将这个开始的节点返回并且用来翻转；

如果这组是最后一组并且正好够K个，那么我们就直接将这组节点进行翻转并且返回翻转之后那个开始的节点；

递归过程就是每次拿这K个的头部到上一次返回的节点(下一组开始的节点)，在这之间做翻转。

class Solution:
    def reverseKGroup(self , head: ListNode, k: int) -> ListNode:
        # write code here
        if head == None&nbs***bsp;head.next == None&nbs***bsp;k==1:
            return head
        count = 0
        next_start = head
        while count != k:
            next_start = next_start.next
            count += 1
            if next_start == None:
                if count == k:
                    while k != 0:
                        tmp = head.next
                        head.next = next_start
                        next_start = head
                        head = tmp
                        k-=1
                    return next_start
                else:
                    return head
            
        next_start = self.reverseKGroup(next_start, k)
        
        while k!=0:
            tmp = head.next
            head.next = next_start
            next_start = head
            head = tmp
            k-=1
        return next_start