链表的左旋和右旋

右旋的定义如下

给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。 
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
 解释:
 向右旋转 1 步: 5->1->2->3->4->NULL
 向右旋转 2 步: 4->5->1->2->3->NULL

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/rotate-list
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这本是一道右旋算法题，但我歪打正着写成了左旋，是用队列实现的，代码如下，注意链表要求是最简单的仅有头指针的单链表

#include<queue>
#include<iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
    
};

ListNode* rotateLeft(ListNode* head, int k) {
    queue<ListNode*> rotater;   //自制循环队列
    int count = 0;  //链表长度计数器
    ListNode* p = head;
    while (p != NULL) {
        rotater.push(p);
        count++;
        p = p->next;
    }
    if (count == 0)    return head;
    if (k % count==0)  return head;
    k = k % count;  //减少循环次数
    for (int i = 0; i < k; i++) {   //开始循环队列
        ListNode* q = rotater.front();
        rotater.pop();
        rotater.push(q);
    }
    //根据循环完的rotater建立链表
    ListNode* myhead = rotater.front();
    rotater.pop();
    p = myhead;
    while (!rotater.empty()) {
        ListNode* n = rotater.front();
        rotater.pop();
        p->next = n;
        p = n;
    }
    p->next = NULL;
    return myhead;
}

这个左旋代码就是借助了队列，将队尾的元素放到队头，就形成一个循环队列结构，但是如果要换成右旋该怎么办呢？这个时候就需要栈出场了，将链表元素先都压进栈，这个时候的出栈序列就是链表末尾元素的序列，将这些末尾元素依次接到队头，就可以实现右旋了。要注意当循环次数大于链表自身长度时，就出现了冗余循环，因为将一个长度为5的队列右旋5次就还原为其自身了，所以可以进行去重。k = k % count，减少循环次数，也可以防止栈空。右旋的代码如下：

#include<stack>
#include<iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
    
};

ListNode* rotateRight(ListNode* head, int k) {
    stack<ListNode*> rotater;   //自制循环队列
    int count = 0;  //链表长度计数器
    ListNode* p = head;
    while (p != NULL) {
        rotater.push(p);
        count++;
        p = p->next;
    }
    if (count == 0)    return head;
    if (k % count==0)  return head; //重复的循环就可以省略了
    k = k % count;  //减少循环次数
    for (int i = 0; i < k; i++) {
        p = rotater.top();  //将栈顶的元素取出作为链表头
        rotater.pop();
        p->next = head;
        head = p;
    }
    rotater.top()->next = NULL; //将最后末尾的剩余在栈的链表末尾置为NULL,防止链表首尾循环
    return head;
}

可以发现其实右旋的代码还简单一些。LeetCode我已经刷了100多题了，LeetCode的难度是远远赶不上CCF认证的第3、4、5题的，但是其实如果深挖 LeetCode 上面的一些题目其实还是很有收获的。不得不说CCF的风格还是和 LeetCode 大不一样，CCF更加偏向实际应用背景，而LeetCode更像传统算法风格。