AC
题目描述：
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 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
算法过程：
思路一：绕圈法。
观察示例可知，所谓翻转这个链表，无非就是把后几个节点挪到前面罢了。容易联想到不过是形成1个圆，然后把新的头返回即可
1）数节点个数
2）连接首尾节点
3）运动到新的头部节点的上一位，断开链表
4）返回新的头部节点
代码：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def rotateRight(self, head, k):
"""
:type head: ListNode
:type k: int
:rtype: ListNode
"""
dummy = ListNode(0)
dummy.next = head
if head is None:
return None
#先数链表有几个节点
i = head
count = 1
while i.next is not None:
i = i.next
count += 1
#抛掉重复的转圈,也算一种算法优化吧
k = k%count
if (k == 0) or count == 1:
return head
#把链表头尾连起来
i.next = head
#从dummy开始运动
i = dummy
#运动到新的链表的头的上一个节点
for _ in range(count - k):
i = i.next
j = i.next
i.next = None
return j
思路二：快慢指针
算法过程
1）定义2个指针，一快一慢
2）快的先走k步，慢的不动
3）接着快慢一起动，当快的走到节点的时候，慢的的下一项就是新的头部节点。
算法证明：
由过程可知，快的永远比慢的快k步，所以当快的指针到尾部节点时，慢的指针距它还有k步远。这时候我们从这里断开链表，则能保证后k个节点移到前面来
代码：
class Solution(object):
def rotateRight(self, head, k):
if not head or not head.next or k==0:
return head
ListLen = 0
p = head
#数有几个节点
while(p):
ListLen+=1
p = p.next
#优化
k = k%ListLen
if k==0:
return head
#快节点先走k步
p = head
while(k>0):
k -=1
p = p.next
slow = head
fast = p
#接着让fast走到最后一个节点，slow与它有着同样的速度
while fast.next:
slow = slow.next
fast = fast.next
#把头尾连起来然后断开链表
new_head = slow.next
fast.next = head
slow.next = None
return new_head
总结：快慢指针，可以达到错位运动的效果，有时能制造很多trick魔法。
