61.旋转链表

struct ListNode* rotateRight(struct ListNode* head, int k){
struct ListNode* fast=head,*slow=head,*temp=head;
    if(!head) return head;
    int count=1;
    while(temp->next)
    {
        temp=temp->next;
        count++;
    }
    k%=count;
    if(k==0) return head;
    k++;
    while(k--) fast=fast->next;
    while(fast)
    {
        fast=fast->next;
        slow=slow->next;
    }
struct ListNode* Head=slow->next;
    slow->next=NULL;
    temp->next=head;
return Head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

思路：将旋转问题转化为将链表倒数k个节点作为链表的新表头
时间复杂度为O（n），空间复杂度为O（1）

struct ListNode* rotateRight(struct ListNode* head, int k){
struct ListNode *temp=head,*p=head;
    if(!head) return head;
    int count=1;
    while(temp->next)
    {
        temp=temp->next;
        count++;
    }
    k%=count;
    if(k==0) return head;
    temp->next=head;
    count-=k;
    while(--count) p=p->next;
    temp=p->next;
    p->next=NULL;
    return temp;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

另一种思路：先把链表连接成环，再确定新的表头，这种方法少了一个while循环
但是不知道为什么，第二种方法执行用时更多，按理来说应该更快