LeetCode 61. Rotate List

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL
解析：
前面的题目是对数组进行循环处理，这次是对链表进行处理。
从示例中可以看到有可能k的数值超过链表长度，所以首先获取链表长度len，然后k%=len，降低计算复杂度。然后观察原始链表和旋转后的链表。
1->2->3->4->5->NULL
4->5->1->2->3->NULL
len=5,k=2
第len-k个元素成为了链表尾部。
具体思路如代码所示：
[cc lang=”C++”]
/**
* 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)
return head;
int len = 1;
ListNode *tail,*new_head;//定义临时节点
tail=new_head=head;
while(tail->next)//计算链表长度
{
tail=tail->next;
len++;
}
k %= len;
tail->next = head;//将链表形成环
for(int i=0; i< len-k; i++) { tail=tail->next;
}
new_head = tail->next;
tail->next = NULL;
return new_head;
}
};
[/cc]
运行结果：

参考：
https://leetcode.com/problems/rotate-list/discuss/22735/My-clean-C++-code-quite-standard-(find-tail-and-reconnect-the-list)