题目

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

分析

从右往左的k的位置，旋转链表。可以先计算总长度L，然后找到L-k的位置。不过要注意k可能大于L，需要先将k%L。给出几个易错的测试数据如下。

/*
[1,2,3,4,5]
4
[1,2,3,4,5]
5
[1,2,3,4,5]
6
[1,2,3,4,5]
7
[1,2]
3
[]
0
[]
1
[1,2,3]
2000000000
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* rotateRight(struct ListNode* head, int k) {
    struct ListNode* p1,*p2;
    p1=head,p2=head;
    //计算链表长度
    int length=0;
    while(p1!=NULL)
    {
        length=length+1;
        p1=p1->next;
    }
    //k值好像可以循环遍历链表，所以求模，减少时间
    if(length==0) return head;
    else if(length==1)
        k=1;
    else
        k=k%length;
    //一个指针从左往右找第K个
    p1=head;
    for(int i=0;i<k;i++)
    {
        if(p1!=NULL&&p1->next!=NULL) p1=p1->next;
        else p1=head;
    }
    if(p1==NULL)
    {
        return head;
    }
    //另一个指针从头开始，则当第一个指针到最后时候，另一个指针到达倒数第k个
    while(p1->next!=NULL)
    {
        p1=p1->next;
        p2=p2->next;
    }
    p1->next=head;
    head=p2->next;
    p2->next=NULL;
    return head;
}