Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.
看到这个题第一秒有点懵,想我们怎么可以知道找到倒数第几个node然后points to head.
随后就想到,哦! 处理List这种情况的套路应该是Fast/Slow pointer, 间隔为K。当Fast为last Node 的时候, Slow刚好 在倒数第K个Node,然后让LastNode指向head。
证明碰到难题的时候不要慌自习想一下还是有突破口的【想思路的时候尽量先不想具体的code】
...
具体实现的时候,发现还有一些事是之前没有考虑进去的。 就是k > List长度的时候的情况
如果是: 1-->2 k = 3的话, 应该变成 2-->1 因为 right rotae once. 2-->1 , right rotate twice 1-->2, Right rotate third, 2-->1
不过经过了一小段尝试,最后的结果是 runtime beat 99.3%
我的做法是先用了一个for loop衡量了一下List的具体长度。 然后用k % 长度得出 真实shift值。这样做的好处是无视掉shift的倍数问题。
【不过我发现我做题的时候竟然有一个趋势是第一次就去追求最优解,这是一个很不好的习惯 一开始我是很拒绝用一个for loop来测定list长度的 害怕时间上会增加 不过没想到这么做还比很多Leetcode大神更快】