题目描述
思路
首先用双指针法向后移动,分别获取链表的最后一个结点和倒数第k的结点,再把这部分连接到链表的头部即可,这部分的操作并不难。
但是实际这样写了之后就会发现,如果链表的长度小于k的话,这样的操作就是行不通的,需要对这种情况进行特殊处理。
但是在处理过程中发现这个操作有这样的特点:当链表长度leng小于k时,将链表旋转k个位置其实就相当于把链表旋转k%leng个位置,即余数个位置。
另外还发现:在链表长度为0、1,以及k为0这些情况下,都不需要进行任何操作。
于是得出下面的代码:
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
//进行特殊情况的处理
if(head == nullptr || k == 0 ){
return head;
}
if(head -> next == nullptr){
return head;
}
ListNode* Dummy = new ListNode(0,head);
ListNode* index1 = new ListNode();
ListNode* index2 = new ListNode();
index1 = Dummy;
index2 = Dummy;
int i = k;
int length = 0;
while(i--){
index2 = index2 -> next;
if(index2 -> next == nullptr){
length = k-i;
break;
//这是链表长度<=k的情况
}
}
if( length){
return rotateRight(head, k%length);
//这样就把长度小于k的情况转化为了下面的一般情况
//因为k除以链表长度的余数一定是小于k的,这样就归到了一般情况里去
}
//一般情况,把后面k个结点连接到链表头部
while(index2 -> next != nullptr){
index1 = index1 -> next;
index2 = index2 -> next;
}
index2 -> next = Dummy -> next;
ListNode* result = index1 -> next;
index1 -> next = nullptr;
return result;
}
};
同时这个思路的时间复杂度不会超过链表的长度,时间上效率也很好。
官方题解: