debug遇到的问题
1.语法之指向指针成员
错误写法：
pivot_start.next=head; //指针存储的是地址
*pivot_start.next=head; //因为'.'的优先级高于'*',所以报错
报错：
request for member 'next' in 'pivot_start', which is of pointer type 'ListNode*' (maybe you meant to use '->' ?)
正确写法：
pivot_start->next=head; //优先选择的写法
//(*pivot_start).next=head;
2.当k大于链表长度的情况下
拿到这题我首先想到的就是用快慢指针来解，快指针先走k步，然后两个指针一起走，当快指针走到末尾时，慢指针的下一个位置是新的顺序的头结点，对翻转连接处处理即可
/**代码遇到用例[1,2],3时报错
* 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) {
int n=0;
if (head==NULL||k==0) //避免n=0，或k=0的多运算
{
return head;
}
ListNode* pivot_start=head;
ListNode* pivot_end=head;
for(int i=0;i<k;i++)
{
if(pivot_start!=NULL)
pivot_start=pivot_start->next;
}
if (pivot_start==NULL)
{
return head;
}
while(pivot_start->next!=NULL)
{
pivot_start=pivot_start->next;
pivot_end=pivot_end->next;
}
pivot_start->next=head; //(*pivot_start).next=head;
head=pivot_end->next; //不能将新的开头丢掉
pivot_end->next=NULL;
return head;
}
};
结果是，代码遇到用例[1,2],3时报错，反映出当k的值大于链表长度时，需要进行特殊处理，将k=k%n对k进行取余，后应用上面的算法，可以通过。
3.单链表翻转
遇到看k>n的情况时，起初误以为需要对链表进行翻转，写了一个翻转代码，此处也mark一下。
{
ListNode* prev=pivot_end;
ListNode* cur=pivot_end->next;
ListNode* temp=pivot_end->next->next;
while(cur)
{
temp=cur->next;
cur->next=prev;
prev=cur;
cur=temp;
}
head->next=NULL;
return prev;
}
我的解法
- 对链表长度进行统计，更新k为链表长度范围内的步数
- 快慢指针同时前移，至快指针移动至链表尾部，找到了要操作的链表节点
- 对链表首尾和连接处进行处理
/**
* 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) {
int n=0;
if (head==NULL||k==0) //避免n=0，或k=0的多运算
{
return head;
}
ListNode* pivot=head;
while(pivot)
{
n++;
pivot=pivot->next;
}
k=k%n;
ListNode* pivot_start=head;
ListNode* pivot_end=head;
for(int i=0;i<k;i++)
{
if(pivot_start!=NULL)
pivot_start=pivot_start->next;
}
if (pivot_start==NULL)
{
return head;
}
while(pivot_start->next!=NULL)
{
pivot_start=pivot_start->next;
pivot_end=pivot_end->next;
}
pivot_start->next=head; //(*pivot_start).next=head
head=pivot_end->next; //不能将新的开头丢掉
pivot_end->next=NULL;
return head;
}
};
最优解法
提交之后发现更快地解法：
- 第一次取链表长度时，将链表尾部与链表头相连，构成一个循环单链表；
- 接下来只需要单指针进行移动操作；
- 找到位子之后也只需要断开此处连接即可。
/**
* 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) return head;
int len=1; // number of nodes
ListNode *newH, *tail;
newH=tail=head;
while(tail->next) {
tail = tail->next;
++len;
}
tail->next = head; // circle the link
k %= len;
for(auto i=0; i<len-k; ++i)
tail = tail->next; // the tail node is the (len-k)-th node (1st node is head)
newH = tail->next;
tail->next = NULL;
return newH;
}
};
