LeetCode-25 K 个一组反转链表

题目

原题 25. K 个一组翻转链表

解题

使用 Rust 解题时, 我们应该关注 Node 节点的所有权转移 (Ownership Transfer), 这也是链表问题在 Rust 场景下的主要难点.

解题思路

1. 对链表进行递归处理 (recursively), 内层已翻转, 外层待调整
2. 在调整链表时, 使用头插法将外层的 node 逐个移动到内层有序结果内
3. 等待所有的外层节点调整完, 当前层级调整结束

Rust 头插法 翻转链表

pub fn reverse_k_group(mut head: Option<Box<ListNode>>, k: i32) -> Option<Box<ListNode>> {
    let mut next_head = &mut head;
    for _ in 0..k {
        if let Some(node) = next_head.as_mut() {
            next_head = &mut node.next;
        } else {
            // 待处理的链表长度不足 k 个, 直接返回头节点
            return head;
        }
    }
    // 将待处理的子链表 take 出来, process it recurisively
    let mut new_head = Self::reverse_k_group(next_head.take(), k);

    // new_head 所在的子链表视为已排序 (内层链表节点)
    // 将 head 所在的外层链表, 使用头插法反转到内层子链表内
    while let Some(mut node) = head {
        head = node.next.take(); // 将外层下一个节点作为 head 节点
        node.next = new_head;    // 原始头节点连接到子链表
        new_head = Some(node);   // 更新子链表头节点
    }

    new_head
}

头插法图解如下