开发递归方法实现ListItem链表的右旋转操作

嘿，我来帮你搞定这个递归实现链表右旋转的问题！首先咱们得先明确下ListItem的基础结构（这里假设是类似Java的实现，你可以根据自己的开发语言调整）：

class ListItem {
    int value; // 可替换为你需要的其他数据类型
    ListItem next;

    ListItem(int val) {
        this.value = val;
        this.next = null;
    }
}

接下来咱们直接上递归实现的核心逻辑：通过递归定位到链表的倒数第二个节点，把最后一个节点抽出来作为新的头节点，让倒数第二个节点的next置空，最后把原链表的头接到新头的后面。

完整递归代码实现 #

public ListItem rotateRight(ListItem head) {
    // 基例：空链表或只有单个节点，不需要旋转，直接返回原链表
    if (head == null || head.next == null) {
        return head;
    }

    // 递归找到最后一个节点，同时断开它和倒数第二个节点的连接
    ListItem newHead = findTailAndDisconnectPrev(head);
    // 把原链表的头节点接到新头的末尾
    newHead.next = head;
    return newHead;
}

// 辅助递归方法：负责找到最后一个节点，并让倒数第二个节点与它断开连接
private ListItem findTailAndDisconnectPrev(ListItem current) {
    // 递归终止条件：当前节点的下一个节点就是链表的最后一个节点
    if (current.next.next == null) {
        ListItem tail = current.next;
        current.next = null; // 断开倒数第二个节点和最后一个节点的关联
        return tail;
    }

    // 递归深入，直到找到符合终止条件的节点
    return findTailAndDisconnectPrev(current.next);
}

逻辑走一遍（以1->2->3->4为例） #

1. 调用rotateRight(1)，因为链表长度大于1，进入辅助方法findTailAndDisconnectPrev(1)
2. 辅助方法中1.next.next是3（非null），递归调用findTailAndDisconnectPrev(2)
3. 同样2.next.next是4（非null），继续递归调用findTailAndDisconnectPrev(3)
4. 此时3.next.next是null（因为3.next是4，4.next为null），取出tail=4，把3.next设为null，返回4
5. 回到rotateRight(1)，把4.next设为1，此时链表变为4->1->2->3，返回4作为新头，完全符合需求！

额外提示 #

如果需要实现多次右旋转（比如旋转k次），可以基于这个单次旋转的逻辑扩展：先计算链表长度，用k取模长度得到有效旋转次数，再循环调用这个方法即可，避免不必要的重复操作。

内容的提问来源于stack exchange，提问作者L.Pju