递归的时间和空间复杂度
bobo老师好。我今天做了一个题目：把链表结点向右旋转k次。比如input是 1->2->3->4->5, k=2，那么输出是 4->5->1->2->3。我用递归完成了这个题目，代码如下
public ListNode rotateRight(ListNode head, int k) {
// write your code here
if (head == null || head.next == null) {
return head;
}
if (k == 0) {
return head;
}
ListNode prev = head;
while (prev.next.next != null) {
prev = prev.next;
}
prev.next.next = head;
head = prev.next;
prev.next = null;
return rotateRight(head, k - 1);
}我的理解是，这段代码的时间复杂度是O(n)，因为递归函数的调用次数跟n有关。而空间复杂度是O(1)，这个我不太确定，因为用到了ListNode prev = head。虽然有ListNode命令，但是并没有new出一个新结点，只是在原来的结点上增加了reference，所以空间复杂度是O(1)。不知道这样的理解是否正确？
第二个问题，关于这段代码，您觉得哪里还有优化的空间呢？谢谢！
正在回答 回答被采纳积分+1
这个代码的时间复杂度是 O(k*n) 的。在递归的过程中，你每次都从头开始遍历整个链表，遍历到链表的结尾，用的时间是 O(n) 的，整个递归过程需要向下 k 层，从 k 直到 0，所以是 O(k*n) 的。
空间复杂度是 O(k) 的，因为递归的层数是 k，所以至少需要 k 的系统栈空间。
==========
先扫描一遍整个链表，得到整个链表的长度 n 和尾结点；
然后，再遍历一遍链表，你就能拿到第 n - k 个节点，和这第 n - k 个节点之前的节点。
对整个链表右旋转 k 次，可以一次完成，即让第 n - k 个节点作为新的头结点，整个链表的尾结点和原先的头节点相连。
这个思路的参考代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0001-0500/0061-Rotate-List/cpp-0061/main.cpp （C++，但思路应该能看懂）。
这个代码是真正的时间是 O(n) 的，空间是 O(1) 的。
==========
进一步，上面的代码扫描了两遍整个链表。第一遍获得链表的总长度，第二遍获得第 n - k 个节点（即倒数第 k 个节点）
而获得链表倒数第 k 个节点，可以用快慢指针的方式，只遍历链表一趟获得。可以参靠这个问题的题解：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/solution/
不过这是一个常数级的优化，整个算法依然是 O(n) 的。
继续加油！：）
相似问题
登录后可查看更多问答，登录/注册
恭喜解决一个难题，获得1积分~
来为老师/同学的回答评分吧
0 星