思想

链表的数据结构基础是用额外的空间存储下一个数据的位置，以此换取不连续内存的存储，进而更高效的使用资源。
同时，链表在增删方面的时间复杂度是 O(1)。
在处理链表相关的问题时，解题重点是搞清楚关系的处理，当前节点和后续节点的关系，和之前节点的关系。在此基础上，往往使用递归的方式能够快速的解题。

实例

K 个一组翻转链表 leetcode 25

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

输入：
（1）head: ListNode，一个链表头结点；
（2）k: int，一组成员的个数；

输出：
ListNode，翻转后的链表的头结点

举例：
当输入 head = [1,2,3,4,5]，k = 2 时，每 2 个元素做一次翻转，不足 2 个的不做处理，返回 [2,1,4,3,5]。

递归

递归的思路是思考反复执行的重复过程，并找到 base case。
这里的递归主体是一组元素的翻转，是不断被重复的，base case 是没有找到完整的一组元素，则正常返回。
上例

1 -> 2 -> 3 -> 4 -> 5 -> None

先从 head 前进一组位置，head = 2, new_head = 3，将 head 之前的部分翻转，然后指向 new_head

new_head <- 1 <- 2  reverse(3 -> 4 -> 5 -> None)

后续重复递归过程，最后 base case 是元素不够一组的数量时

2 -> 1 -> 4 -> 3    -> 5 -> None

编码

from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverse_nodes_in_k_group(head: Optional[ListNode], k: int) -> Optional[ListNode]:
    # 处理边界条件
    if head is None:
        return head
    # 初始化
    start = new_start = head
    for _ in range(k):
        if new_start is None:
            # 元素不足，不反转求 new_head，直接返回当前 head，正序
            return head
        new_start = new_start.next
    # 组内翻转
    pre, cur = None, start
    while cur != new_start:
        tmp = cur.next
        cur.next = pre
        pre = cur
        cur = tmp
    new_head = pre
    # 连接本组最后一个元素和后续递归的头结点
    start.next = reverse_nodes_in_k_group(new_start, k)
    # 返回翻转后的头结点
    return new_head