链表旋转问题：实现右旋转k位的解决方案

链表作为数据结构之一，在编程中经常遇到各种操作需求。其中，链表旋转操作是比较经典且有趣的题目。本文将详细介绍如何实现链表右旋转k位的功能，并通过示例和代码实现来阐述解决方案。

问题描述

给定一个链表，旋转链表的右k位。这里的k是一个非负整数。需要注意的是，当k大于链表长度时，实际旋转的次数应取模运算后的结果。

示例分析

示例1： 输入链表为1→2→3→4→5→NULL，k=2。

输出链表为4→5→1→2→3→NULL。

解释：第一次右旋转后为5→1→2→3→4→NULL，第二次右旋转后即为4→5→1→2→3→NULL。

示例2： 输入链表为0→1→2→NULL，k=4。

输出链表为2→0→1→NULL。

解释：每次右旋转后链表结构如下：

第一次：2→0→1→NULL

第二次：1→2→0→NULL

第三次：0→1→2→NULL

第四次：2→0→1→NULL

从上述示例可以看出，链表旋转操作具有周期性，旋转k次后结果与旋转k mod n次后结果相同，其中n为链表的长度。

解题思路

解决链表旋转问题可以通过双指针法来实现。具体来说，我们可以使用一个快指针和一个慢指针来遍历链表。快指针从头节点开始，跳过k个节点，而慢指针则从头节点开始，逐步移动。当快指针到达旋转点时，慢指针的位置即为新的头节点。

关键点分析

边界条件处理：

如果链表为空或k为0，则无需旋转，直接返回原链表。

快指针遍历：

快指针从头节点出发，跳过k个节点。这里需要注意的是，如果k大于链表长度，应取模运算后再进行计算。

慢指针定位：

当快指针移动到旋转点时，慢指针的位置即为新的链表头。然后，将链表分为两部分，调整指针的位置以完成旋转。

代码实现

ListNode* rotateRight(ListNode* head, int k) {
    if (head == nullptr || k == 0) return head;
    // 使用双指针法解决问题
    ListNode* dup = new ListNode(-1);
    dup->next = head;
    ListNode* fast = dup;
    // 计算链表长度
    int count = 0;
    while (fast->next != nullptr) {
        fast = fast->next;
        count++;
    }
    // 计算实际旋转次数
    int n = count - (k % count);
    ListNode* slow = dup;
    while (n > 0) {
        slow = slow->next;
        n--;
    }
    // 调整指针
    fast->next = dup->next;
    dup->next = slow->next;
    slow->next = nullptr;
    return dup->next;
}

代码解释

边界条件检查：

首先检查链表是否为空或k是否为0，如果是，直接返回原链表。

创建辅助节点：

为了简化操作，我们创建一个辅助节点dup，使得操作更灵活。

计算链表长度：

使用快指针fast遍历链表，计算链表的总长度count。

计算实际旋转次数：

由于旋转k次后结果与旋转k mod count次后结果相同，所以计算实际需要旋转的次数n。

定位慢指针：

使用慢指针slow从dup开始，移动n次，到达旋转点。

调整链表指针：

将fast指针的下一个节点设置为dup的下一个节点，调整dup和slow的指针，完成旋转。

通过上述步骤，我们就可以实现链表右旋转k位的功能。这种方法不仅时间复杂度为O(n)，空间复杂度为O(1)，效率很高，而且代码实现简单易懂。

转载地址：http://zybbz.baihongyu.com/

你可能感兴趣的文章