该文章是本人的第一篇，略有忐忑，不好，勿喷；有误，请指教，谢谢！
这篇是一个来自leetcode的算法题，关于数据结构链表的，不算难，本文简略概述下解析过程及校对过程。
题目：旋转链表
示例1：
输入: 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
示例2：
输入: 0->1->2->NULL, k = 4
输出: 2->0->1->NULL
解释:
向右旋转 1 步: 2->0->1->NULL向右旋转 2 步: 1->2->0->NULL向右旋转 3 步:0->1->2->NULL
向右旋转 4 步:2->0->1->NULL
解题过程：
第一次解答代码：
/**
* 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) {
ListNode* p = head;
int num = 0;
while((p!=NULL)&&(p->next != NULL))
{
num++;
p = p->next;
}
num++;
if(p) p->next = head;
int steps = 0;
while(num < k)
num += num;
steps = num - k;
for(int i = 0;i < steps;i++)
{
if(p)
p = p->next;
}
ListNode* newhead = NULL;
if(p)
{
newhead = p->next;
p->next = NULL;
}
return newhead;
}
};
第一次解析完成后，感觉信息满满，必能通过，谁知告知如下结果：
提示超出了执行时间超时~
仔细观察，修改上述代码中的红色部分，进行了下面的解答。
第二次解答：
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
ListNode* p = head;
int num = 0;
while((p!=NULL)&&(p->next != NULL))
{
num++;
p = p->next;
}
num++;
if(p) p->next = head;
int steps = 0;
steps = num - k % num;
for(int i = 0;i < steps;i++)
{
if(p)
p = p->next;
}
ListNode* newhead = NULL;
if(p)
{
newhead = p->next;
p->next = NULL;
}
return newhead;
}
};
修改完红色部分后，提交，通过~
备注：红色部分修改的是从原链表尾节点寻找新链表尾节点所需走的步数。
参考校验：
自己提交通过后，浏览了下别人的解答，发现有改进的地方，请看下文。
参考代码：
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(!head) return head;
int len=1; // number of nodes
ListNode *newH, *tail;
newH=tail=head;
while(tail->next) // get the number of nodes in the list
{
tail = tail->next;
len++;
}
tail->next = head; // circle the link
if(k %= len)
{
for(auto i=0; i<len-k; i++) tail = tail->next; // the tail node is the (len-k)-th node (1st node is head)
}
newH = tail->next;
tail->next = NULL;
return newH;
}
};
反观自己的代码，缺少了第一行的判断头节点是否为空，对照两份代码，可以看到，加上头节点的判空逻辑可以省略后面的多次判空。
附注解题思路：
1、寻找到原链表的尾节点，并同时计算链表长度
2、连接尾节点与头节点，即：尾节点的下一个节点为头节点，此时链表成环
3、计算新链表尾节点的位置（从原链表尾节点倒走k，则等同于正走n-k,n为链表长度，而如果n<k,则n=n+n,直到n>k）
4、从原链表的尾节点走第三步计算出的步数，即可得到新链表的尾节点
5、先标识出新链表的头节点，即：新链表的尾节点的下一个节点,之后断开环
如果觉得《链表算法小解》对你有帮助，请点赞、收藏，并留下你的观点哦！
