2020小红书：每K个一组反转链表[python][递归]

python20行，O(n)算法，无额外空间开销。需要两个辅助函数：

• reverse(h, k)：给定一个头节点和k，反转至多k个节点，返回反转后的头节点、下一段的头节点和已反转数；
• reverse_k(head, k):按K个每组反转链表，返回反转后的头节点；

1. reverse(h, k)就是单纯反转链表，没什么可说的；
2. reverse_k(head, k)需要加一个判断，调用reverse(h, k)进行反转后，如果本组反转量小于k个，则再次调用reverse(h, k)撤销反转，详见代码。

1. 首先是给出链表的数据结构和读题目的IO，并根据IO构建链表，没什么好说的，大家都能写：

# --- 构建链表BEG ---#
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

v = list(map(int, input().split()))
k = int(input())

head = ListNode(None)
pre = head
for i in v:
    c = ListNode(i)
    pre.next = c
    pre = c
head = head.next
# --- 构建链表END ---#

2. 算法核心，详见开头。

def reverse(h, k):
    pre, c, cnt, tail = None, h, 0, h
    while c and cnt<k: # 翻转节点
        cnt += 1
        temp = c.next
        c.next, pre, c = pre, c, temp
    return pre, c, cnt # 此时, pre 为逆转后的头节点, c为下一段的头节点, cnt为已逆转的个数


def reverse_k(head, k):
    if head is None:
        return None# 返回头和尾
    tail = head
    head, next_head, cnt = reverse(head, k)

    if cnt == k:
        next_head = reverse_k(next_head, k)# 逆转下一组
        tail.next = next_head # 本组的尾接下一组的头
    else:
        head, _, _ = reverse(head, k) # 取消逆转操作
    return head

3. 输出，没啥可说的：

# --- output ---#
head = reverse_k(head, k) # 反转链表

while head: # output
    print(head.val, end=" ")
    head = head.next