NC211. 旋转链表
描述
示例1
输入:
{1,2,3,4,5},2
输出:
{4,5,1,2,3}
示例2
输入:
{1,2,3},3
输出:
{1,2,3}
C++ 解法, 执行用时: 3ms, 内存消耗: 384KB, 提交时间: 2022-03-08
class Solution {
public:
ListNode* rotateLinkedList(ListNode* head, int k) {
if(head==nullptr)
return head;
ListNode *p=head;
int n=0;
while(p){//计算链表长度
n++;
p=p->next;
}
k%=n;//取余运算
if(k==0)
return head;
int cnt=n-k;
p=head;
for(int i=0;i<cnt;i++){
p=p->next;
}
vector<int> v;//辅助数组
while(p){
v.push_back(p->val);
p=p->next;
}
p=head;
for(int i=0;i<cnt;i++){
v.push_back(p->val);
p=p->next;
}
p=head;
for(int i=0;i<n;i++){//新值覆盖旧值
p->val=v[i];
p=p->next;
}
return head;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-03-14
class Solution {
public:
ListNode* rotateLinkedList(ListNode* head, int k) {
if(head==nullptr)
return head;
ListNode *p=head;
int n=0;
while(p){//计算链表长度
n++;
p=p->next;
}
k%=n;//取余运算
if(k==0)
return head;
int cnt=n-k-1;//向右遍历的长度-1
p=head;
while(cnt--){
p=p->next;
}
ListNode *q=p->next;//新的首节点
p->next=nullptr;//尾结点结束标记
ListNode *t=q;
p=q->next;
while(p){
t=p;
p=p->next;
}
t->next=head;//拼接链表
return q;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-02-18
/**
* 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) {
ListNode* p=head;
ListNode* Head=new ListNode(-1),*tail=Head;
int len=0;
while(p){
len++;
p=p->next;
}
if(len==0)
return Head->next;
k%=len;
len-=k;
int ww=len;
p=head;
while(ww--){
p=p->next;
}
while(p){
tail->next=p;
tail=p;
p=p->next;
}
while(len--){
tail->next=head;
tail=head;
head=head->next;
}
tail->next=NULL;
return Head->next;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-02-09
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
/*
方法一：快慢指针
其实就是求链表的倒数第k个节点，然后以它为头结点返回，把原始链表的尾连接上原始链表的头。
但是这个k可能比原始链表要大，所以得先求出链表的长度，然后k对链表长度取余再进行算法流程。
*/
ListNode* rotateLinkedList(ListNode* head, int k) {
if(head == NULL) return head;
// 先求链表倒数第k个节点
ListNode* cur = head;
int n = 0;
while(cur != NULL){
cur = cur->next;
n++;
}
k %= n;
//快指针先移动k-1步
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;
}
};
C++ 解法, 执行用时: 3ms, 内存消耗: 396KB, 提交时间: 2022-01-12
/**
* 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) return head;
// int length = 0;
// // k 可能超过链表长度（开始没考虑到）
// ListNode* tmp = head;
// while(tmp) {
// tmp = tmp->next;
// length++;
// }
// k = k % length;
// int n = k+1;
// // 多走一步，是p2移动到要被挪动的前一个位置
// ListNode* p1 = head;
// ListNode* p2 = head;
// while(n-- && p1) {
// p1 = p1->next;
// }
// if (!p1) return head;
// while(p1) {
// p1 = p1->next;
// p2 = p2->next;
// }
// stack<ListNode*> sk;
// // 将该节点之后的保存进栈（后进先出），顺便将后面节点删除
// while(p2->next) {
// ListNode* next = p2->next;
// sk.push(next);
// p2->next = p2->next->next;
// }
// ListNode* p = nullptr;
// // 将栈中节点弹出，接到最开头节点
// while(!sk.empty()) {
// p = sk.top();
// p->next = head;
// head = p;
// sk.pop();
// }
// return head;
// if(head==nullptr||head->next==nullptr||0==k) return head;
// ListNode *tmp=head,*tmp2;
// int num=0;
// //利用指针每次走两步，快速定位到结尾
// while(tmp->next!=nullptr&&tmp!=nullptr) tmp=tmp->next->next,++num;
// if(tmp==nullptr) num=2*num;
// else num=2*num+1;
// k%=num;//k可能大于num，所以需要先取余
// if(k==0) return head;//k%num==0,说明移动链表总长度的倍数相当于没移动
// tmp=head,tmp2=head;
// if(!(k&1)) {//k是偶数,直接让tem每次走两步，走k/2步就到了第k个了。
// k/=2;
// while(k>0) tmp=tmp->next->next,--k;
// }
// else {//k是奇数，tmp每次走两步，走k/2步后再走一步就到第k个了
// k/=2;
// while(k>0) tmp=tmp->next->next,--k;
// tmp=tmp->next;
// }
// //然后每次两个都只走一步，直到前面的到达null，然后直接修改指针指向
// while(tmp->next!=nullptr) tmp=tmp->next,tmp2=tmp2->next;
// tmp->next=head;//将尾节点指向头节点
// head=tmp2->next;//将头指针指向慢走的下一个作为新表头
// tmp2->next=nullptr;//将慢指针的下一个指向nullptr
// return head;
if (!head) return head;
int len = 0;
ListNode* p = head;
while(p) {
p = p->next;
len++;
}
k %= len;
p = head;
while(p->next) {
p = p->next;
}
p->next = head;
int n = len - k;
while(n--) {
p = p->next;
}
ListNode* res = p->next;
p->next = nullptr;
return res;
}
};