61. 旋转链表

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。

Example:

输入: 1->2->3->4->5->NULL, k = 2

输出: 4->5->1->2->3->NULL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int getListNodeLength(struct ListNode * head){
    struct ListNode * head1 = head;
    int len = 0;
    while(head1){
        len++;
        head1 = head1->next;
    }
    return len;
}
struct ListNode*  getPosition(struct ListNode* head, int index){
    if(index < 0) return NULL;
    struct ListNode * head1 = head;
    while(index){
        head1 = head1->next;
        index--;
    }
    return head1;
}

struct ListNode* rotateRight(struct ListNode* head, int k) {
    int len = getListNodeLength(head);
    if(len <=1 || (k %= len) < 1) return head;
    int position = len-k-1;
    struct ListNode* oldlast = getPosition(head,len-1);
    struct ListNode* newhead = getPosition(head,position+1);
    struct ListNode* newlast = getPosition(head,position);
    oldlast->next = head;
    newlast->next = NULL;
    return newhead;
}
思路:

该题看似是循环n次，实则将后K个元素移至头结点的位置。

直接找到最后一个元素，将它指向开始的位置。将倒数第k+1个元素指向NULL。

k可以大于链表的长度，所以要对链表长度取模。