rotatelayer list rotate什么意思 leetcode

来源：蜘蛛抓取(WebSpider) 时间：2016-06-04 04:03 标签： rotate是什么意思
拒绝访问 |
| 百度云加速
请打开cookies.
此网站 () 的管理员禁止了您的访问。原因是您的访问包含了非浏览器特征(38fd7-ua98).
重新安装浏览器，或使用别的浏览器标签：至少1个，最多5个
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.
其实这题的描述有些不妥当，确切的说是将最右侧的节点依次移到最左侧作为头结点，一直移动到右侧第k个节点后结束。还是以1-&2-&3-&4-&5-&NULL为例k=1
结果为：5-&1-&2-&3-&4-&NULLk=2
结果为：4-&5-&1-&2-&3-&NULLk=3
结果为：3-&4-&5-&1-&2-&NULLk=4
结果为：2-&3-&4-&5-&1-&NULLk=5
结果为：1-&2-&3-&4-&5-&NULLk=6
结果为：5-&1-&2-&3-&4-&NULL
换句话说 当k的值超过了list的长度len的时候，移动k次等价于移动k%len次
思路一：计算出list长度
即通过一次遍历，找到列表的末节点同时，计算出列表的长度。根据列表的长度，计算k%len，也就是最短等价移动次数。之后利用双指针，保证头指针和尾指针之间的距离始终为k，从而找到右边第k个节点。
public ListNode rotateRight2(ListNode head, int k) {
if(k==0 || head==null)
//get list length and last node
ListNode last =
int len = 1;
while(last.next != null){
last = last.
ListNode start = new ListNode(0);
start.next =
int count = len-k;
while(count & 0){
start = start.
last.next =
head = start.
start.next =
思路二：简单优化
其实在某些情况下，k的值并不一定比数组的长度大。这时候还计算数组的长度的话，反而降低了性能。这个时候，可以将遍历的过程和头指针的移动结合起来。如果头指针移动到结尾而k并不是等于0，则可以得知k大于列表长度，同时这个过程还可以得出列表的长度。如果k等于0时，头指针未移动到末尾，则可以继续头指针和尾指针的同时移动，知道头指针到达数组的最后一个元素。代码如下：
public ListNode rotateRight(ListNode head, int k) {
if(head == null){
ListNode firstPointer =
int length = 0;
while(firstPointer!= null && k & 0){
firstPointer = firstPointer.
if(k == 0){
if(firstPointer == null){
ListNode secondPointer =
while(firstPointer != null && firstPointer.next!=null){
secondPointer = secondPointer.
firstPointer = firstPointer.
firstPointer.next =
ListNode result = secondPointer.
secondPointer.next =
return rotateRight(head, k%length);
0 收藏&&|&&0
你可能感兴趣的文章
本作品采用 署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可
思路二在k小于len的测试用例较多的情况下，效率更高
分享到微博？
技术专栏，帮你记录编程中的点滴，提升你对技术的理解收藏感兴趣的文章，丰富自己的知识库
明天提醒我
我要该，理由是：LeetCode OJ（25）
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
class Solution {
ListNode* rotateRight(ListNode* head, int k) {
if (head == NULL || head-&next == NULL || k == 0)
ListNode *p =
ListNode *tail = NULL;
ListNode *newhead = NULL;
ListNode *newtail = NULL;
int len = 0;
while (p-&next != NULL)
int num = k %
if (num == 0 || num == len)
int count = 1;
while (count & (len - num ))
newtail = newtail-&
newhead = newtail-&
tail-&next =
newtail-&next = NULL;
刚开始把题目意思理解错了，以为k代表的是链表下标，然后发现多次提交之后，给出的例子貌似有冲突。于是百度了一下该题正确的意思，发现是旋转k的节点。然后思路就很清晰了
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：53963次
积分：1709
积分：1709
排名：千里之外
原创：123篇
(2)(2)(6)(3)(1)(5)(23)(15)(6)(4)(1)(5)(9)(10)(26)(6)LeetCode（178）
把链表循环右移k个单位
先算出链表长度，然后把末尾节点指向头节点，然后再从头节点右移length - k 个单位，得到新链表的头指针，并设置末尾的空节点
* Definition for singly-linked list.
* struct ListNode {
ListNode *
ListNode(int x) : val(x), next(NULL) {}
class Solution {
ListNode* rotateRight(ListNode* head, int k) {
int length = 1;
if (!head)
return NULL;
ListNode *temp =
while (head -& next)
head = head -&
//cout && length &&
head -& next =
int zz = length -
while (zz && head)
head = head -&
temp = head -&
head -& next = NULL;
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：96076次
积分：4842
积分：4842
排名：第5862名
原创：403篇
转载：36篇
(1)(27)(61)(41)(21)(3)(29)(11)(21)(70)(2)(3)(7)(12)(17)(33)(39)(20)(12)(9)

我要回帖

更多关于 rotate是什么意思 的文章

 

随机推荐