Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
61. Rotate List.go
61. Rotate List_test.go
README.md

README.md

61. Rotate List

题目

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL 

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL 

题目大意

旋转链表 K 次。

解题思路

这道题需要注意的点是,K 可能很大,K = 2000000000 ,如果是循环肯定会超时。应该找出 O(n) 的复杂度的算法才行。由于是循环旋转,最终状态其实是确定的,利用链表的长度取余可以得到链表的最终旋转结果。

这道题也不能用递归,递归解法会超时。

You can’t perform that action at this time.