题目描述
将一个链表每个节点向右循环移动 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
解析
实现技巧
仔细观察循环右移结果，可以发现规律，一个包含n个元素的链表每个结点循环移动k个位置实际上就是链表中的后k（k = k%n）个结点组成的链表与前n-k个结点组成的链表互换。
实现方法
- 统计链表结点个数，并且记录当前链表最后一个结点
- 计算确认k
- 找到前n-k个结点，确定新的第一个结点和最后一个结点
- 操作结点的next引用组成新链表
代码图示
上面实现方法第三步执行后，代码中的引用如图指向各个结点。第四步是分别操作链表两部分的指向关系。
image.png
代码
private class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public ListNode rotateRight(ListNode head, int k) {
if(null == head || k <= 0){
return head;
}
/*统计链表结点个数，并且记录当前链表最后一个结点*/
ListNode tail = head;
int n = 1;
while(tail.next != null){
tail = tail.next;
n++;
}
/*计算确认k*/
k = k % n;
if(0 == k){
return head;
}
/*找到前n-k个结点，确定新的第一个结点和最后一个结点*/
ListNode newTail = head;
for(int i = 1 ; i < n - k; ++i){
newTail = newTail.next;
}
ListNode newHead = newTail.next;
/*操作结点的next引用组成新链表*/
newTail.next = null;
tail.next = head;
return newHead;
}
总结
一些看似很复杂的需求可能往往存在一些简单的解法。例如本例中，假如循环k次，每次把所有结点移动一位，这样实现起来会相当复杂，并且容易出错。而实际上找到其中规律，前n-k个结点组成的链表和后k个结点组成的链表交换位置即可，实现和编码都变得简单。因此在实际生产中需要不断总结，优化自己的代码质量和算法效率。
