首页 > 代码库 > 每日算法之四十三:Rotate List (列表旋转k个元素)
每日算法之四十三:Rotate List (列表旋转k个元素)
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可能是比链表长度要大的数字,因此实际旋转的位置就是k%len(list)。如果这个计算结果等于零或者等于len(list),列表是不用旋转的。
接下来如果是事例给出的正常情况,那么有三步就能完成旋转。
(1)第一个辅助指针从头开始后移k个位置。
(2)这时第二个辅助指针指向头指针,然后两个指针同时向后移动,知道第一个辅助指针指向尾节点。
(3)声明第三个辅助指针指向第二个辅助指针的后继结点作为将要返回的新头指针。把第二个指针的后继设为空指针,同时将第一个指针的后继指向原先的有指针。这儿样就能完成指针的旋转。
注:最后给出的另外另种方式更简洁高效,推荐先看一下。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *rotateRight(ListNode *head, int k) { if(head == NULL || k <= 0) return head; ListNode *temp = head; int node_count = 0; while(temp != NULL) { node_count++; temp = temp->next; } if(k > node_count) k = k%node_count; if(k == node_count || k == 0) return head; ListNode *first = head; while(/*first != NULL && first->next != NULL &&*/ k > 0) { first = first->next; k--; } //if(k > 0) // return head; ListNode *second = head; while(first->next != NULL) { first = first->next; second = second->next; } ListNode *newhead = second->next; first->next = head; second->next = NULL; return newhead; } };
这里有一个地方需要注意,在第一次完成的时候没有代码中的取余部分,因为没有考虑到循环移位的位数比链表长度长的情况,因此,在加上取余部分后,原代码中(即现在注释掉的部分)是不再需要的。因为这个时候的k一定比链表长度要小。因此这些判断是不在需要的。
下面是一些网上的答案,贴出来以供下次参考。
ListNode *rotateRight(ListNode *head, int k) { // Start typing your C/C++ solution below // DO NOT write int main() function if (head == NULL || head->next == NULL || k == 0) { return head; } int length = 0; ListNode *ptr = head, *tail = head; while (ptr != NULL) { length++; tail = ptr; ptr = ptr->next; } k %= length; ptr = head; for (int i = 0; i < length - k - 1; i++) { ptr = ptr-> next; } tail->next = head; head = ptr->next; ptr->next = NULL; return head; }另一种更简洁的方式。
ListNode *rotateRight(ListNode *head, int k) { if(head==NULL)return NULL; ListNode *p=head; int n=0; while(p->next) { p=p->next; n++; } n++; k=k%n; p->next=head; ListNode *q=head; for(int i=0;i<n-k-1;i++) q=q->next; head=q->next; q->next=NULL; return head; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。