[LeetCode]61.Rotate List

本文主要是介绍[LeetCode]61.Rotate List，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【题目】

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;}
};

【思路三】

/*-------------------------------------------------------------------
*   日期：2014-04-08
*   作者：SJF0115
*   题目: 61.Rotate List
*   来源：https://leetcode.com/problems/rotate-list/
*   结果：AC
*   来源：LeetCode
*   总结：
--------------------------------------------------------------------*/
#include <iostream>
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;}//ifint size = 0;ListNode *p = head,*right = head;// 统计节点个数while(p){++size;p = p->next;}//while// 找到右移的节点k = size - k % size;// 未右移if(k == size){return head;}//ifListNode *pre = nullptr;for(int i = 0;i < k;++i){pre = right;right = right->next;}//forpre->next = nullptr;p = right;// 到最后一个节点while(p->next){p = p->next;}//whilep->next = head;return right;}
};
int main() {Solution solution;int A[] = {1,2,3,4,5};ListNode *head = new ListNode(-1);ListNode *node;ListNode *pre = head;for(int i = 0;i < 5;i++){node = new ListNode(A[i]);pre->next = node;pre = node;}//forhead = solution.rotateRight(head->next,2);while(head){cout<<head->val<<" ";head = head->next;}//whilecout<<endl;return 0;
}

运行时间：

这篇关于[LeetCode]61.Rotate List的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---