链表旋转算法实现

"这篇文档是关于旋转链表的算法题解，主要讲解如何将一个给定的链表向右移动指定位置k。" 在IT技术领域，尤其是算法设计与分析中，旋转链表是一个常见的面试题，它考察了对链表操作的理解以及问题解决能力。该题目的目标是给定一个链表的头节点head和一个整数k，将链表中的每个节点向右移动k个位置。具体来说，如果k是链表长度n的倍数，链表保持不变；否则，链表的末k个节点将成为新的头部。 例如，给定链表`[1,2,3,4,5]`，若k=2，原链表变为`[4,5,1,2,3]`；对于链表`[0,1,2]`，k=4时，由于k是链表长度的两倍，所以链表保持不变，输出依然为`[0,1,2]`。 解决这个问题的一个C++实现如下： ```cpp class Solution { public: ListNode* rotateRight(ListNode* head, int k) { if (k == 0 || head == nullptr || head->next == nullptr) { return head; } int n = 1; ListNode* iter = head; // 计算链表长度 while (iter->next != nullptr) { iter = iter->next; n++; } // 求出实际需要移动的步数，即n - (n % k) int add = n - k % n; if (add == n) { return head; // 如果k是链表长度的倍数，无需旋转 } // 将链表尾部连接到头部，形成循环链表 iter->next = head; // 移动指针，找到新的头部 while (add--) { iter = iter->next; } // 断开循环，返回新的头部 ListNode* ret = iter->next; iter->next = nullptr; return ret; } }; ``` 这段代码首先检查特殊情况（k为0或链表为空或只有一个节点），这些情况下不需要旋转。接着，计算链表的长度n，并确定实际需要移动的步数add。如果add等于n，表示k是链表长度的倍数，直接返回原链表。否则，将链表尾部连接到头部，形成一个循环链表，然后通过迭代找到新的头部，最后断开循环，返回新头部。 这个解决方案的时间复杂度是O(n)，空间复杂度是O(1)，因为它只使用了常数级别的额外空间。这种高效的方法是解决链表旋转问题的常见思路。在面试或实际编程任务中，理解并能正确实现这样的算法是至关重要的，因为它展示了对链表操作的深入理解和巧妙运用。