将给定的链表向右转动k个位置，k是非负数。
例如：
给定1->2->3->4->5->null ， k=2，
返回4->5->1->2->3->null。
[编程题]转动链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
/*
题目;给定一个链表，将链表旋转到右边的k个位置，其中k是非负的。
例如:
1->2->3->4->5->NULL,为K = 2，
返还4->5->1->2->3->NULL。
*/
/*
分析：先遍历一遍，得出链表长度len，注意k可能会大于len，因此k%=len。
将尾结点next指针指向首节点，形成一个环，接着往后跑len-k步，从这里断开，就是结果
*/
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
if(head==nullptr||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=nullptr;//断开环
return head;
}
};
发表于 2017-07-24 16:03:50
回复(3)
这道题主要先理解题意，就是倒着数k个node，从那开始到结尾和之前那部分对调，那个例子就是，4->5拿前面来，1->2->3拿后面去。
package go.jacob.day817; /** * 61. Rotate List * @author Jacob */ public class Demo2 { /* * 这种方法考虑了k=0的情况。 * 当k=0，cur和pre都为链表最后一个节点 * 运行cur.next = preHead.next;preHead.next = pre.next;pre.next = null;后 * 链表结构没有改变 */ public ListNode rotateRight(ListNode head, int k) { if (k == 0 || head == null || head.next == null) return head; ListNode preHead = new ListNode(0); preHead.next = head; ListNode cur = head; ListNode pre = head; int total; for (total = 1; cur.next != null; total++) cur = cur.next; for (int i = 1; i < total - k % total; i++) { pre = pre.next; } cur.next = preHead.next; preHead.next = pre.next; pre.next = null; return preHead.next; } }
发表于 2017-08-17 10:57:55
回复(1)
public class Solution {
/*
* 思路：
* 分析可看出，要得到结果，其实就是修改几个节点间链接关系，具体包括以下三点：
* 1.末尾节点指向头结点，2.倒数第n个元素为头结点，3.倒数第n+1个元素指向null
*/
public ListNode rotateRight(ListNode head, int n) {
if(head==null) return null; //若链表为空，则直接返回null
if(n==0) return head; //若 n 为0，则直接返回链表本身
int count = 1; //用来计数：传入的链表的节点个数
ListNode p = head;
while(p.next!=null) { //直到 p 找到链表末尾节点，停止循环
p = p.next;
count++;
}
p.next = head; //末尾节点指向头结点，整个链表成为一个环
if(n>count) n=n%count;
for(int i=0; i<count-n; i++) { //通过循环让p指向倒数第n+1个元素
p = p.next;
}
head = p.next; //倒数第n个元素为头结点
p.next = null; //倒数第n+1个元素为末尾节点，指向null
return head;
}
}
发表于 2019-01-02 14:15:44
回复(2)
题目：输入k和链表的头结点，循环右移链表的后K个结点。
For example:
Given1->2->3->4->5->NULLand
k
=2,
return4->5->1->2->3->NULL.
思路：
1.首先要找链表的倒数第K个结点；
2.因循环右移的K个结点仍是按原来顺序排列，可考虑用一个先进先出的容器 即队列 将 后K个结点
存储，依次连接在链表首处；
3.但此解法空间复杂度为O(k);
4.将链表首尾相接成环，然后在第K个结点前的结点处断开即可；
因leetcode上测试用例中的k有大于length of list 的情况，故要先遍历一遍然后使k=k%(length of list),
时间复杂度仍为O(n).
代码如下：
public class Solution {
public ListNode rotateRight(ListNode head, int n) {
if(head==null||head.next==null)
return head;
//测试用例中有n大于length of list的情况；
ListNode temp=head;
int count =1;
while(temp.next!=null)
{
temp=temp.next;
count++;
}
n=n%count;
if(0 == n)
return head;
ListNode first=head;
ListNode second=head;
//先找到倒数第n个结点；
int num=1;
while(num<n&&second!=null)
{
second=second.next;
num++;//while循环中一定要注意别少了对变量的修改，避免进入死循环；
}
//firstpre记录倒数第n个结点的上一个结点;
ListNode firstpre=first;
while(second.next!=null)
{
firstpre=first;
first=first.next;
second=second.next;
}
second.next=head;
head=first;
firstpre.next=null;
return head;
}
}
发表于 2016-05-09 19:01:32
回复(0)
/*
* 目的：滚动链表
* 方法：
* 1.求链表长度，同时记下尾结点
* 2.计算滚动次数k=k%len
* 3.将链表在len-k除截断，然后将后面一部分接到前面
*/
ListNode *rotateRight(ListNode *head, int k) {
if (head==nullptr||head->next == nullptr||k<=0){
return head;
}
int len = 0;
ListNode*p = head,*tail=nullptr;
while(p){
if (p->next == nullptr)
tail = p;
p=p->next;
len++;
}
k = k%len;
ListNode dummy(-1);
dummy.next = head;
ListNode*pre = &dummy;
for (int i = 0; i < (len-k);++i){
pre = pre->next;
}
tail->next = dummy.next;
dummy.next = pre->next;
pre->next = nullptr;
return dummy.next;
}
发表于 2019-12-09 20:42:56
回复(0)
/**
* 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 || k==0 || !head->next) return head;
//ListNode *root = new ListNode(-99999);
//root->next = head;
ListNode *cur = head;
int n = 1;
//得到链表长度
while(cur->next){
cur = cur->next;
n += 1;
}
//首尾相连
cur->next = head;
int left = n-k % n;
//继续跑n-k步
while(left--){
cur = cur->next;
}
head = cur->next;
cur->next = NULL;
return head;
}
};
发表于 2019-06-24 23:05:35
回复(0)
public class Solution {
public ListNode rotateRight(ListNode head, int n) {
if(head == null || head.next == null || n == 0) {
return head;
}
ListNode cur = head;
int index = 0;
int length = 0;
//链表长度
while(cur != null) {
cur = cur.next;
length++;
}
cur = head;
//倒数第n个节点，正数是第 length-n 个节点
//题意里会循环查找，n可能比链表长，需要取模运算，找到断开的节点
while(++index != length-n%length) {
cur = cur.next;
}
//当前节点是尾节点，说明倒数节点为头结点，无需翻转，直接返回
if(cur.next == null) {
return head;
}
//断开处的节点
ListNode newHead = cur.next;
cur.next = null;
cur = newHead;
//遍历到尾部
while(cur.next != null) {
cur = cur.next;
}
//两段链表相连
cur.next = head;
return newHead;
}
}
编辑于 2017-12-22 23:18:27
回复(0)
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k)
{
if(head==nullptr || k<=0)
return head;
ListNode *p=head;
int len = 0;
while(p)
{
++len;
p = p->next;
}
k = k%len;
if(k==0) return head;
ListNode *fast = head,*slow = head;
for(int i=0;i<k;i++)
fast = fast->next;
while(fast->next)
{
slow = slow->next;
fast = fast->next;
}
ListNode *newHead = slow->next;
slow->next = nullptr;
fast->next = head;
return newHead;
}
};
发表于 2017-07-14 12:02:23
回复(0)
简直在试答案嘛！测试用例有超过链表长度情况，所以要首先求链表长度len，然后n对len求余
就是找到倒数第k个结点，改变指针就可以了
public class Solution {
public ListNode rotateRight(ListNode head, int n) {
if(head == null || head.next == null)
return head;
ListNode tmp = head;
int len = 0;
while(tmp != null){
len++;
tmp = tmp.next;
}
n = n % len;
if(n == 0)
return head;
ListNode cur = head;
ListNode fast = head;
ListNode slow = head;
for(int i = 0; i < n; i++){
if(fast != null)
fast = fast.next;
else
return null;
}
// 这是当n==len的情况
if(fast == null)
return head;
// 找到倒数第k个结点的前一个结点slow
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
// slow的next是新的head
ListNode newhead = slow.next;
slow.next = null;
fast.next = cur;
return newhead;
}
}
编辑于 2017-05-23 16:36:24
回复(3)
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
if(head == NULL || head->next == NULL || k <= 0) return head;
ListNode* pNode = head;
int len = 0;
ListNode* tail;
while(pNode != NULL) {
len++;
if(pNode->next == NULL) tail = pNode;
pNode = pNode->next;
}
tail->next = head;
pNode = tail;
int idx = len - (k % len);
while(idx > 0) {
idx--;
pNode = pNode->next;
}
ListNode* phead = pNode->next;
pNode->next = NULL;
return phead;
}
};
发表于 2017-03-10 09:27:44
回复(0)
class Solution {
public:
ListNode *rotateRight(ListNode *head, int k) {
int length = 0;
ListNode *p = head;
ListNode *last = NULL;
while(p)
{
length ++;
last = p;
p = p->next;
}
if(length == 0 || k==0) return head;
k= k%length;
ListNode *newhead = head;
last->next = head;
for(int i=k;i<length;i++){
p = newhead;
newhead = newhead->next;
}
p->next = NULL;
return newhead;
}
};
发表于 2016-09-17 20:22:16
回复(1)
public class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head==null||k==0)
return head;
int len = 0;
ListNode cur = head;
ListNode last = null;
while(cur!=null){
len++;
last = cur;
cur = cur.next;
}
if(k>=len&&len!=0)
k %= len;
if(k==0)
return head;
last.next = head;//形成环路
cur = head;//因为是右移动，所以从头开始遍历到倒数第k个元素
for(int i = 1;i<=len-k;i++){
last = cur;
cur = cur.next;
}
//cur是头
last.next = null;
return cur;
}
}
发表于 2016-06-03 23:05:05
回复(1)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode rotateRight (ListNode head, int k) {
// write code here
if(head==null || k==0) return head;
//双指针
ListNode slow = head;
ListNode fast = head;
while(k>0){
if(fast == null) fast=head;
fast =fast.next;
k--;
}
if(fast == null) return head;
while(fast.next!=null){
slow=slow.next;
fast=fast.next;
}
ListNode temp =slow.next;
slow.next=null;
fast.next=head;
return temp;
}
}
发表于 2022-01-14 01:00:03
回复(0)
class Solution {
public:
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* rotateRight(ListNode* head, int k) {
// write code here
int i;
if(!head||!head->next) return head;//special case
//Determine the length of the list
ListNode *pi=head;
for(i=0;pi;i++){
pi=pi->next;
}
while(i<k){k=k-i;}
if(k==0) return head;
//use fast-slow points to find the last k elements
ListNode* vhead=new ListNode(-1);
vhead->next=head;
ListNode *pre_fast, *fast, *pre_slow=vhead, *slow=pre_slow->next;
pre_fast=pre_slow->next;
for(i=1;i<k;i++){pre_fast=pre_fast->next;}
slow=pre_slow->next;
fast=pre_fast->next;
while(fast){
pre_fast=pre_fast->next;
pre_slow=pre_slow->next;
slow=slow->next;
fast=fast->next;
}
//break and link two parts
pre_slow->next=NULL;
pre_fast->next=vhead->next;
return slow;
}
};
public:
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* rotateRight(ListNode* head, int k) {
// write code here
int i;
if(!head||!head->next) return head;//special case
//Determine the length of the list
ListNode *pi=head;
for(i=0;pi;i++){
pi=pi->next;
}
while(i<k){k=k-i;}
if(k==0) return head;
//use fast-slow points to find the last k elements
ListNode* vhead=new ListNode(-1);
vhead->next=head;
ListNode *pre_fast, *fast, *pre_slow=vhead, *slow=pre_slow->next;
pre_fast=pre_slow->next;
for(i=1;i<k;i++){pre_fast=pre_fast->next;}
slow=pre_slow->next;
fast=pre_fast->next;
while(fast){
pre_fast=pre_fast->next;
pre_slow=pre_slow->next;
slow=slow->next;
fast=fast->next;
}
//break and link two parts
pre_slow->next=NULL;
pre_fast->next=vhead->next;
return slow;
}
};
发表于 2021-11-09 05:12:47
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
//注意一个地方，他说的是向右转,那么指针就是向左走
public ListNode rotateRight (ListNode head, int k) {
// write code here
//思路：用头尾指针进行操作
if(head==null)return head;
ListNode tail = head;
int len=1;
while(tail.next!=null){
tail = tail.next;
len++;
}
k = len - k%len;
// for(int i=0;i<k;i++){
// tail.next = head1;
// head1 = head.next;
// tail = tail.next;
// tail.next =null;
// }
tail.next=head;
for(int i=0;i<k ;i++){
tail = tail.next;
}
head = tail.next;
tail.next = null;
return head;
}
}
发表于 2021-03-14 21:34:35
回复(0)
ListNode tail = new ListNode(-1);
ListNode newHead = new ListNode(-1);
public ListNode rotateRight (ListNode head, int k) {
// write code here
if (head == null || k==0){
return head;
}
newHead.next = head;
rotateRightHelper(head,k);
tail.next.next = head;
return newHead.next;
}
public void rotateRightHelper (ListNode head, int k) {
if(head.next == null){
tail.next = head;
return;
}
rotateRight(head.next,k-1);
if(k == 0){
newHead.next = head.next;
head.next = null;
}
}
ListNode newHead = new ListNode(-1);
public ListNode rotateRight (ListNode head, int k) {
// write code here
if (head == null || k==0){
return head;
}
newHead.next = head;
rotateRightHelper(head,k);
tail.next.next = head;
return newHead.next;
}
public void rotateRightHelper (ListNode head, int k) {
if(head.next == null){
tail.next = head;
return;
}
rotateRight(head.next,k-1);
if(k == 0){
newHead.next = head.next;
head.next = null;
}
}
发表于 2021-01-14 12:40:22
回复(1)
基本思路：
- 先求链表长度n，然后
k = k mod n - 将链表首尾相连
- 找到新的head的前一个节点，断链，返回新head
代码如下：
//
// Created by jt on 2020/9/26.
//
class Solution {
public:
/**
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* rotateRight(ListNode* head, int k) {
// write code here
// 如果只有0个或1个节点
if (!head || k == 0) return head;
// 将k与链表长度取模
int n = 1;
ListNode *p = head, *q = head;
while (p->next) { ++n; p = p->next; }
k %= n; k = n - k;
// 找到新链表头节点的前一个节点
while (--k > 0) { q = q->next; }
// 合链
p->next = head;
// 断链
ListNode *newHead = q->next;
q->next = nullptr;
return newHead;
}
};
发表于 2020-09-26 18:21:27
回复(0)
我其实使用了一个取巧的方法，将链表所有元素都遍历一遍，然后使用列表的方法，最后一位删除一位元素然后初始再添加一位元素，直到计数达到k；操作完后，再构造一个链表就可以了
class ListNode: def __init__(self, x): self.val = x self.next = None class Link: def __init__(self): self.head = None def addlink(self,val): node1=ListNode(val) if self.head==None: self.head=node1 return else: cur=self.head while(cur.next): cur=cur.next cur.next=node1 return # # # @param head ListNode类 # @param k int整型 # @return ListNode类 # class Solution: def rotateRight(self, head, k): # write code here if head == None&nbs***bsp;k == 0: return head totallist=[] while(head): totallist.append(head.val) head=head.next while(k): totallist.insert(0,totallist.pop()) k-=1 l1=Link() for i in totallist: l1.addlink(i) return l1.head
发表于 2020-09-22 11:07:18
回复(1)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
* 思路：将一个链表从待旋转节点分开，如 1 -> 2 -> 3 -> 4 ->5 旋转2次的结果 4 ->5 -> 1 -> 2 -> 3
* 可以看做 4->5 + 1 -> 2 -> 3,即从3的位置分开
* @param head
* @param k
* @return
*/
public ListNode rotateRight(ListNode head, int k) {
// 不旋转
if (head == null || k == 0) {
return head;
}
// 获取链表长度
ListNode cur = head;
int len = 0;
while (cur != null) {
cur = cur.next;
len++;
}
k = k % len;
// 不旋转
if (k == 0) {
return head;
}
// pre为待旋转节点的前一个节点
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
int now = 0;
while (pre != null) {
pre = pre.next;
now++;
if (now == len - k) {
break;
}
}
ListNode tempNode = pre.next;
pre.next = null;
// 开始旋转
ListNode secondDummy = new ListNode(0);
secondDummy.next = tempNode;
while (tempNode.next != null) {
tempNode = tempNode.next;
}
tempNode.next = dummy.next;
return secondDummy.next;
}
}
编辑于 2020-08-02 12:22:57
回复(0)
public ListNode rotateRight (ListNode head, int k) {
if (head == null || k == 0){
return head;
}
//获取链表长度
ListNode p = head;
int len = 1;
while (p.next != null){
len++;
p = p.next;
}
//计算旋转后的头部位置
k = len - k%len;
//尾部指向头部
p.next = head;
//接着找到旋转k后的头
for (int i = 0; i < k; i++) {
p = p.next;
}
//设置新head,断开环
head = p.next;
p.next = null;
return head;
}
发表于 2020-07-26 14:31:22
回复(0)
问题信息
难度：
86条回答
48收藏
16338浏览
通过挑战的用户
查看代码-
2022-11-30 11:25:44
-
2022-09-14 17:33:02
-
2022-09-12 16:38:43 -
2022-08-20 16:18:59
-
2022-08-10 21:08:27
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
