将给定的链表向右转动k个位置，k是非负数。
例如：
给定1->2->3->4->5->null ， k=2，
返回4->5->1->2->3->null。
[编程题]转动链表
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)
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)
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)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode rotateRight(ListNode head, int n) {
if(head == null || head.next == null || n == 0)
return head;
int len = 0;
ListNode temp = head;
//遍历到链表尾部，得到链表长度
while(temp != null){
temp = temp.next;
len ++;
}
if(n == len)
return head;
if(n > len){
n = n % len;
}
int index = len - n;
ListNode pre = null;
ListNode cur = head;
while(cur != null && index > 0){
pre = cur;
cur = cur.next;
index --;
}
pre.next = null; //中间断链
ListNode newhead = cur;
while(cur.next != null){
cur = cur.next;
}
cur.next = head; //原链表尾部指向原链表头部
return newhead;
}
}
发表于 2020-06-20 18:05:34
回复(0)
public class Solution {
public ListNode rotateRight(ListNode head, int n) {
if(head == null || head.next == null || n <= 0){
return head;
}
ListNode start = head, end = head;
for(int i = 0; i< n; i++){
end = end.next;
if(end == null){
end = head;
}
}
if(end == head){
return head;
}
while(end.next != null){
start = start.next;
end = end.next;
}
ListNode tmp = start.next;
start.next = null;
end.next = head;
return tmp;
}
}
发表于 2018-05-10 17:22:45
回复(0)
public class Solution {
public ListNode rotateRight(ListNode head, int n) {
if (head == null)
return head;
ListNode slow = head;
ListNode fast = head;
for (int i = 0; i < n; i++) {
fast = fast.next;
if (fast == null)
fast = head;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
fast.next = head;
ListNode newH = slow.next;
slow.next = null;
return newH;
}
}
发表于 2018-03-17 21:35:12
回复(0)
public class Solution {
public ListNode rotateRight(ListNode head, int n) {
if(head==null||head.next==null)return head;
for(int i =1;i<=n;i++){
ListNode p = head;
ListNode p1=head;
ListNode p2 = null;
while(p1.next!=null){
if(p1.next.next==null){
p2 =p1;
}
p1=p1.next;
}
p2.next=null;
p1.next=p;
head=p1;
}
return head;
}
}
发表于 2017-12-09 20:28:49
回复(0)
//首先要看k的值是否大于链表长度，如果大于链表长度，则取余确定右边第几个节点为head
//将最后一个节点的next指向原来的head，这样成为了一个环，
//之后遍历到新head的前一个节点将前一个节点的next赋值为null，最后返回新head
public class Solution {
public ListNode rotateRight(ListNode head, int n) {
if(head == null || n < 0){
return head;
}
int length = 1;
ListNode node = head;
//获得链表长度
while(node.next!=null){
++length;
node = node.next;
}
//获得右边第i个下标
int k = n % length;
//将最后一个节点指向head，形成一个环
node.next = head;
//接下来的遍历节点数
int num = length - k;
for(int i=0;i<num;i++){
node = node.next;
}
//得到新节点
head = node.next;
node.next = null;
return head;
}
}
发表于 2017-09-05 16:43:58
回复(1)
public class Solution {
public ListNode rotateRight(ListNode head, int n) {
ListNode p = head,end = null; int num = 0;
if(p==null)return p;
while(p!=null){
num++;
end = p;
p = p.next;
}
if(n%num == 0)return head;
int i = 1; p = head;
while(i < num-n%num){
p = p.next;
i++;
}
ListNode q = p.next;
end.next = head;
p.next = null;
return q;
}
}
发表于 2017-08-14 20:49:12
回复(1)
public class Solution {
public ListNode rotateRight(ListNode head, int n) {
if(head == null || n == 0)
return head;
int num = 1;
ListNode cur = head;
while(cur.next != null) {
num++;
cur = cur.next;
}
n %= num;
if(n == 0)
return head;
cur.next = head;
for(int i=0; i<num-n; i++) {
cur = cur.next;
}
head = cur.next;
cur.next = null;
return head;
}
}
发表于 2017-06-20 16:02:28
回复(0)
使用快慢指针，先找到倒数第n个节点，然后改变指针
public static ListNode rotateRight(ListNode head, int n) {
if (head == null) //空
return null;
ListNode fast, slow; //快慢指针
fast = slow = head;
int lenOfList = getLen(head); //获取链表长度
int k = n % lenOfList; //取余
if (k == 0) //不变
return head;
for (int i = 0; i < k; i++) {
fast = fast.next;
}
//slow指向前半段的最后一个,fast指向后半段最后一个
while (fast.next != null){
fast = fast.next;
slow = slow.next;
}
ListNode newHead = slow.next;
slow.next = null; //变成最后一个
fast.next = head; //连上head
return newHead;
}
//获取链表长度
private static int getLen(ListNode head) {
ListNode p = head;
int len = 0;
while (p != null){
len++;
p = p.next;
}
return len;
}
发表于 2017-04-11 23:02:28
回复(0)
Since n may be a large number compared to the length of list. So we need to know the length of linked list.After that, move the list after the (l-n%l )th node to the front to finish the rotation.
Ex: {1,2,3} k=2 Move the list after the 1st node to the front
Ex: {1,2,3} k=5, In this case Move the list after (3-5%3=1)st node to the front.
So the code has three parts.
-
Get the length
-
Move to the (l-n%l)th node
3)Do the rotation
public ListNode rotateRight(ListNode head, int n) { if (head==null||head.next==null) return head; ListNode dummy=new ListNode(0); dummy.next=head; ListNode fast=dummy,slow=dummy; int i; for (i=0;fast.next!=null;i++)//Get the total length fast=fast.next; for (int j=i-n%i;j>0;j--) //Get the i-n%i th node slow=slow.next; fast.next=dummy.next; //Do the rotation dummy.next=slow.next; slow.next=null; return dummy.next; }
发表于 2017-03-12 12:25:42
回复(0)
问题信息
难度：
14条回答
49收藏
18338浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
