题解 | #转动链表#

题目描述：将给定的链表向右转动k个位置，k是非负数。
例如：给定1->2->3->4->5->null ， k=2，返回4->5->1->2->3->null。
示例1：
        输入：{1,2},1
        返回值：{2,1}
思路：将给定的链表向右旋转k个位置，若链表为空则直接返回该链表；若链表不为空，则首先需要计算出链表的长度len，当k是链表长度len的整数倍时返回链表即可，反之需要令k%=len,然后遍历链表到第（len-k）个节点并截断，之后将两段连接上即可得到转动后的链表。具体代码如下：

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* rotateRight(ListNode* head, int k) 
    {
        // write code here
        if(head == NULL) return NULL;
        else
        {
            ListNode *res = (ListNode*)malloc(sizeof(ListNode)),*p = head;
            int len=0;
            while(p != NULL)
            {
                len++;//统计链表的长度，即链表中元素的个数
                p = p->next;
            }
            if(k <= 0 || (k % len == 0))
                return head;
            else
            {
                if(len == 1) return head;
                k %=len;
                int n=0;
                p = head;
                ListNode *q;
                while(n <=(len-k) && p != NULL)
                {
                    n++;
                    if(n == (len - k))
                    {
                        q = p->next;
                        p->next = NULL;
                        break;
                    }
                    p = p->next;
                }
                res->next = q;
                while(q != NULL)
                {
                    if(q->next == NULL)
                        break;
                    q = q->next;
                }
                q->next = head;
                return res->next;
            }
        }
    }
};