题目

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 andk=2,

return 4−>5−>1−>2−>3−>NULL.

分析

给定一个链表，以及一个整数k，返回链表右旋k个元素后的结果。

要使得链表右旋k个元素，也就是说明链表后（k）个元素将成为新链表的前半部分，原链表的前（len−k）个元素将成为新链表的后半部分；

此时原链表的head前恰好有k 个元素，即完成了右旋k个位置。

要注意的是，当k=0||n∗len时，原链表将不变，只有当k的结果为 1 len−1时，链表才会发生变化。

AC代码

/**

 * 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 == NULL)

            return head;

        ListNode *p = head;

        //求链表的长度

        int len = 0;

        while (p)

        {

            len++;

            p = p->next;

        }

        k %= len;

        //k<=0时，原链表不旋转

        if (k <= 0)

            return head;

        int index = 1;

        //寻找右旋k位置后，链表的首结点

        p = head;

        while (index < (len - k) && p->next != NULL)

        {

            index++;

            p = p->next;

        }

        ListNode *ret = p->next, *q = p;

        //原链表寻找尾结点，将其链接到head

        while (p->next)

            p = p->next;

        p->next = head;

        //前部分尾结点设为NULL

        q->next = NULL;

        return ret;

    }

};

GitHub测试程序源码