给定链表的头节点，旋转链表，将链表每个节点往右移动 k 个位置，原链表后 k 个位置的节点则依次移动到链表头。
即，例如链表 ： 1->2->3->4->5 k=2 则返回链表 4->5->1->2->3
数据范围：链表中节点数满足 
， 
[编程题]旋转链表
其实就是求链表的倒数第k个节点，然后以它为头结点返回，把原始链表的尾连接上原始链表的头。但是这个k可能比原始链表要大，所以得先求出链表的长度，然后k对链表长度取余再进行算法流程。
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode rotateLinkedList (ListNode head, int k) {
if(head == null) return head;
// 先求链表倒数第k个节点
ListNode cur = head;
int n = 0;
while(cur != null){
n ++;
cur = cur.next;
}
k %= n;
ListNode fast = head;
for(int i = 0; i < k - 1; i++){
fast = fast.next;
}
ListNode slow = head;
ListNode prev = new ListNode(-1);
prev.next = slow;
while(fast.next != null){
prev = prev.next;
slow = slow.next;
fast = fast.next;
}
prev.next = null;
fast.next = head;
return slow;
}
}
发表于 2021-12-15 18:18:20
回复(0)
循环一次，记录要操作的地址和链表长度
然后操作就好了
本题要求不高，所以我嫌麻烦直接开了个数组记（其实只记要用的几个地址就够了）
class Solution {
public:
ListNode* rotateLinkedList(ListNode* head, int k) {
int len=0;
ListNode* address[1010];
ListNode *cur=head;
while (cur)
{
address[len++]=cur;
cur=cur->next;
}
if(len==0)
return head;
k%=len;
address[len-k-1]->next=nullptr;
address[len-1]->next=head;
return address[len-k];
}
};
发表于 2023-03-05 21:13:40
回复(1)
struct ListNode* rotateLinkedList(struct ListNode* head, int k ) {
if(head==NULL)
{
return NULL;
}
struct ListNode* head1=head;
int len = 1;
while(head1->next)
{
head1=head1->next;
len++;
}
if(len==1)
{
return head;
}
k%=len;
head1->next=head;
int n = len-k;
struct ListNode* prev=NULL;
while(n)
{
prev=head;
head=head->next;
n--;
}
prev->next=NULL;
return head;
}
发表于 2024-03-31 22:36:45
回复(1)
public ListNode rotateLinkedList (ListNode head, int k) {
if (head == null || head.next == null || k <= 0) {
return head;
}
int length = 1;
ListNode curr = head;
while (curr.next != null) {
length++;
curr = curr.next;
}
curr.next = head;
k = k % length;
if (k == 0) {
return head;
}
for (int i = 0; i < length-k-1; i++) {
head = head.next;
}
ListNode newHead = head.next;
head.next = null;
return newHead;
}
发表于 2024-04-27 18:27:38
回复(0)
1. 根据之前所学的链表反转的方法；可以先将链表整个反转；
2. 然后遍历计数，在k位置断开（也就是令节点为空，令为空前先记录一下后半段的链表开始）把链表分为前半段和后半段，是独立的两个链表，针对对立的两个链表再做链表反转；
3. 最后将第1个的为与第二个链表的头想连接即可
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
//链表反转
ListNode* reverse(ListNode* head) {
ListNode* h = new ListNode(0);
ListNode* temp;
while (head != nullptr) {
temp = head;
head = head->next;
temp->next = h->next;
h->next = temp;
}
return h->next;
}
ListNode* rotateLinkedList(ListNode* head, int k) {
// write code here
if(head==nullptr) return nullptr;
int n = 0;
int cnt = 0;
//把整个链表反转
head = reverse(head);
ListNode* h = head;
//计算整个链表长度，因为k有可能大于n
while (h != nullptr) {
h=h->next;
n++;
}
//k取模
k%=n;
ListNode* end=head;
while (end != nullptr) {
cnt++;
if (cnt == k) {//找到断开位置
break;
}
end=end->next;
}
//断开位置的下一个就是第二个链表的起始位置
ListNode* secondstart=end->next;
//链表断开
end->next=nullptr;
//对第一个链表进行反转
ListNode* first=reverse(head);
ListNode* ans=first;
//找到第一个链表的尾部（且不为空）
while(first->next!=nullptr){
first=first->next;
}
//对第二个链表进行反转
secondstart=reverse(secondstart);
//cout<<secondstart->val<<" "<<secondstart->next->val;
//将第一个链表的尾部和第二个链表的头相连接
first->next=secondstart;
return ans;
}
};
发表于 2024-04-27 17:15:24
回复(0)
遍历
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* rotateLinkedList(ListNode* head, int k) {
// write code here
// 算出节点数量
ListNode* temp = head;
int len = 0;
while(temp)
{
temp = temp->next;
++len;
}
k %= len;
if(k==0 || head==nullptr)
return head;
// 新链表头的前一个
ListNode* t_1 = head;
// 新链表头
ListNode* t_2 = head;
// 原来链表的最后一位
ListNode* t_3 = head;
// 从下标 1 开始
int t = 1;
while(t<len)
{
// 新链表头的前一个
if(t<len-k)
t_1 = t_1->next;
// 新链表头
if(t<=len-k)
t_2 = t_2->next;
// 原来链表的最后一位
t_3 = t_3->next;
++t;
}
// cout << t_1->val << ", " << t_2->val << ", " << t_3->val << endl;
t_1->next = nullptr;
t_3->next = head;
return t_2;
}
};
发表于 2024-04-25 18:35:51
回复(0)
快慢指针：
public static ListNode rotateLinkedList(ListNode head, int k) {
// write code here
if (head == null || head.next == null)
return head;
ListNode slow = head, fast = head;
ListNode preSlow = new ListNode(-1);
preSlow.next = head;
ListNode tmp = head;
int cnt = 0;
while (tmp != null) {
tmp = tmp.next;
cnt++;
}
k %= cnt;
for (int i = 0; i < k - 1; i++) {
fast = fast.next;
}
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
preSlow = preSlow.next;
}
// 断开
preSlow.next = null;
// 拼接
fast.next = head;
// 返回新头部
return slow;
}
发表于 2024-04-24 15:02:20
回复(0)
确定倒数第k个节点就好了
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* rotateLinkedList(ListNode* head, int k) {
// write code here
ListNode* pre = head;
ListNode* topk = head;
int num = 0;
while(pre){
num++;
pre = pre->next;
}
int restnum = k % num;
if(restnum == 0 || head == nullptr)return head;
for (int i = 0; i < num - restnum - 1; i++) {
topk = topk->next;
}
if (topk) {
ListNode* tempk = topk->next;
pre = tempk;
topk->next = nullptr;
while (tempk) {
if (tempk->next == nullptr) {
tempk->next = head;
break;
} else {
tempk = tempk->next;
}
}
return pre;
}
else{
return head;
}
}
};
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* rotateLinkedList(ListNode* head, int k) {
// write code here
ListNode* pre = head;
ListNode* topk = head;
int num = 0;
while(pre){
num++;
pre = pre->next;
}
int restnum = k % num;
if(restnum == 0 || head == nullptr)return head;
for (int i = 0; i < num - restnum - 1; i++) {
topk = topk->next;
}
if (topk) {
ListNode* tempk = topk->next;
pre = tempk;
topk->next = nullptr;
while (tempk) {
if (tempk->next == nullptr) {
tempk->next = head;
break;
} else {
tempk = tempk->next;
}
}
return pre;
}
else{
return head;
}
}
};
编辑于 2024-04-19 16:30:52
回复(0)
public ListNode rotateLinkedList (ListNode head, int k) {
// write code here
ListNode res = new ListNode(0);
res.next = head;
ListNode fast = res;
ListNode front = null;
ListNode slow = res;
ListNode cur = head;
int length = 1;
if ( head == null || head.next == null) return head;
//判断链表长度
while (cur.next != null) {
length++;
cur = cur.next;
}
//对长度进行取余得到有效变换的长度
int j = k % length;
for (int i = 0; i < j; i++) {
fast = fast.next;
}
while (fast != null) {
front = slow;
slow = slow.next;
fast = fast.next;
}
front.next = null;
res.next = slow;
while (slow.next != null) {
slow = slow.next;
}
slow.next = head;
return res.next;
}
发表于 2024-04-10 17:07:43
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode rotateLinkedList (ListNode head, int k) {
// write code here
int num = getNodeNum(head);
if (num == 0 || k % num == 0) return head;
k = k % num;
ListNode dummyHead = new ListNode(-1);
dummyHead.next = head;
ListNode fast = dummyHead;
while (k-- > 0) {
fast = fast.next;
}
ListNode slow = dummyHead;
while (fast.next != null) {
slow = slow.next;
fast = fast.next;
}
ListNode rotateHead = slow.next;
slow.next = null;
fast.next = dummyHead.next;
return rotateHead;
}
public int getNodeNum(ListNode head) {
int res = 0;
while (head != null) {
res++;
head = head.next;
}
return res;
}
}
编辑于 2023-12-18 13:41:41
回复(0)
if(head==NULL)//空链表的特殊情况
return head;
struct ListNode * p=head;
int length=0;
while(p)//遍历链表求表长
{
p=p->next;
length++;
}
p=head;
while(p->next)//遍历链表找到表尾
{
p=p->next;
}
p->next=head;//使链表成为循环链表
p=head;
for(int i=0;i<length-k%length;i++)//找到旋转后的表头
{
p=p->next;
}
struct ListNode * result=p;
for(int i=0;i<length-1;i++)
{
p=p->next;
}
p->next=NULL;//遍历新链表使表尾指针指空，接触循环链表
return result;
发表于 2023-04-25 17:22:53
回复(0)
先让链表变成一个环，然后找到要返回的头结点，再把环断开。
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode rotateLinkedList (ListNode head, int k) {
// write code here
if(head == null) return null;
int i = 1;
ListNode cur = head;
int len = 0;
while(cur.next != null){
cur = cur.next;
len++;
}
len++;
cur.next = head;
while(i <= len - (k % len)){
cur = head;
head = head.next;
i++;
}
cur.next = null;
return head;
}
}
发表于 2023-04-21 10:23:55
回复(0)
package main
import _"fmt"
import . "nc_tools"
/*
* type ListNode struct{
* Val int
* Next *ListNode
* }
*/
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
func rotateLinkedList( head *ListNode , k int ) *ListNode {
if head==nil{
return nil
}
arr:=[]*ListNode{}
for p:=head;p!=nil;p=p.Next{
arr=append(arr,p)
}
n:=len(arr)
k%=n
arr=append(arr[n-k:],arr[:n-k]...)
for i,p:=range arr{
if i+1<n{
p.Next=arr[i+1]
}else{
p.Next=nil
}
}
return arr[0]
}
发表于 2023-03-07 21:09:40
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param k int整型
* @return ListNode类
*/
ListNode* rotateLinkedList(ListNode* head, int k) {
// write code here
if(head == nullptr)
return head;
ListNode* node = head;
// 下面是计算结点个数 为了对k进行取模 防止k过大
ListNode* ttmm = head;
int num = 0;
while(ttmm)
{
num++;
ttmm=ttmm->next;
}
// 求得的了num也就是结点的个数， 对k进行取模
k = k % num;
// 找到需要移动的位置
for(int i=0; node != NULL && i<k; i++)
{
node = node->next;
}
// 这不不是必须的，因为前面已经取模了，所以不会出现node为null的情况
if(!node)
return head;
ListNode* cur = head;
ListNode* tmp = new ListNode(-1);
tmp->next = head;
ListNode* pre = tmp;
// 求一个断点前的指针，断点后的指针
while(node!=NULL)
{
node = node->next;
cur = cur->next;
pre = pre->next;
}
// 知道位置之后 至今进行重新凭借就可以 注意下面的k-1这个点
pre->next = nullptr;
ListNode* node2 = cur;
for(int i=0; i<k-1; i++)
{
node2 = node2->next;
}
node2->next = head;
return cur;
}
};
发表于 2022-09-07 09:52:42
回复(0)
class Solution: def rotateLinkedList(self , head: ListNode, k: int) -> ListNode: # write code here if not head: return None length = 0 temp = head while temp.next: length += 1 temp = temp.next temp.next = head k = k % (length+1) temp = head for _ in range(length-k): temp = temp.next head = temp.next temp.next = None return head
发表于 2022-07-24 22:56:46
回复(0)
class Solution {
public:
ListNode* rotateLinkedList(ListNode* head, int k) {
// write code here
if(!head)return nullptr;
ListNode*pMove=head,*root=nullptr;int n=1;
while(pMove->next)
{pMove=pMove->next;n++;}
pMove->next=head;
pMove=head;int h=n-k%n;
while(--h)pMove=pMove->next;
root=pMove->next;pMove->next=nullptr;
return root;
}
};
public:
ListNode* rotateLinkedList(ListNode* head, int k) {
// write code here
if(!head)return nullptr;
ListNode*pMove=head,*root=nullptr;int n=1;
while(pMove->next)
{pMove=pMove->next;n++;}
pMove->next=head;
pMove=head;int h=n-k%n;
while(--h)pMove=pMove->next;
root=pMove->next;pMove->next=nullptr;
return root;
}
};
发表于 2022-01-02 11:16:45
回复(0)
public ListNode rotateLinkedList (ListNode head, int k) {
if (head == null) return null;
ListNode p = head, slow = head, fast = head,
pref = head, pres = head;
int len = 0;
while (p != null) {
p = p.next;
len++;
}
k %= len; // 长度处理
// 快慢指针找倒数第k个结点 记录快慢指针的前驱
while (k-- > 0) fast = fast.next;
while (fast != null) {
pref = fast;
pres = slow;
fast = fast.next;
slow = slow.next;
}
// 处理一下重新连接
pres.next = null;
pref.next = head;
return slow;
}
发表于 2021-12-29 14:36:03
回复(0)
class Solution: def rotateLinkedList(self , head: ListNode, k: int) -> ListNode: # write code here if head == None: return head n = 1 fast = head while fast and fast.next: fast = fast.next n += 1 # # 找到第k个节点，注意count是从1开始 fast,last = head,head k = k % n for i in range(k-1): fast = fast.next # tmp就是倒数第k+1个节点, last是倒数第k个节点，first就是最后一个节点 tmp = None while fast.next: tmp = last last = last.next fast = fast.next tmp.next = None # 断开链表，首尾重新相接 fast.next = head head = last return head
发表于 2021-12-21 18:37:32
回复(0)
问题信息
难度：
18条回答
27收藏
1628浏览
通过挑战的用户
查看代码-
2022-09-25 10:33:22
-
2022-09-20 14:24:38
-
2022-09-15 00:06:52 -
2022-09-14 02:09:29 -
2022-09-13 23:13:02
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
