【题目】
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,注意 k 可能大于 len,因此令 k% = len。将尾节点 next 指针
指向首节点,形成一个环,接着往后跑 len - k 步,从这里断开,就是要求的结果了。
【代码1】
/********************************* * 日期:2014-01-29 * 作者:SJF0115 * 题号: Rotate List * 来源:http://oj.leetcode.com/problems/rotate-list/ * 结果:AC * 来源:LeetCode * 总结: **********************************/ #include <iostream> #include <stdio.h> #include <algorithm> using namespace std; 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; } int count = 1; ListNode *pre = head,*cur; //统计节点个数,找到尾节点串成一个环 while(pre->next != NULL){ count++; pre = pre->next; } //串成一个环 pre->next = head; //k可能大于链表长度 k = k % count; int index = 1; pre = cur = head; //右移k位 while(index <= (count - k)){ pre = cur; cur = cur->next; index++; } //新的首尾节点 pre->next = NULL; head = cur; return head; } }; int main() { Solution solution; int A[] = {1,2,3,4,5}; ListNode *head = (ListNode*)malloc(sizeof(ListNode)); head->next = NULL; ListNode *node; ListNode *pre = head; for(int i = 0;i < 5;i++){ node = (ListNode*)malloc(sizeof(ListNode)); node->val = A[i]; node->next = NULL; pre->next = node; pre = node; } head = solution.rotateRight(head->next,6); while(head != NULL){ printf("%d ",head->val); head = head->next; } return 0; }
【代码2】
class Solution { public: ListNode *rotateRight(ListNode *head, int k) { if (head == NULL || k == 0) return head; int len = 1; ListNode* p = head; while (p->next) { // 求长度 len++; p = p->next; } k = len - k % len; p->next = head; // 首尾相连 for(int step = 0; step < k; step++) { p = p->next; //接着往后跑 } head = p->next; // 新的首节点 p->next = NULL; // 断开环 return head; } };