LeetCode 61. 旋转链表

题目描述

---

分析

grq：关于链表结点的修改顺序：改前先用，用后就改。
将每个结点向右移动k个位置，实际上就是将后k个结点连接到头部。这道题目是不需要dummy结点的。整体分析如下：

首先要获得整个链表也是后k个结点的尾结点。由于整个是n个结点，除掉后k个结点后还有n-k个结点，要修改指针首先要跳到倒数第k+1个结点（正数第n-k个结点），从第一个结点跳n-k-1次就可以到达。之后就是指针的修改：

• 尾结点指向头结点
• 倒数第k个变为新的头结点
• 倒数第k+1（正数第n-k）个结点变为尾结点指向null，

---

代码（Java）

class Solution {public ListNode rotateRight(ListNode head, int k) {if (head == null) return head;ListNode tail = head;// 先求出链表长度int n = 1;while (tail.next != null) {n ++;tail = tail.next;}k %= n;if (k == 0) return head;ListNode cur = head;// 倒数第k+1个结点成了尾结点for (int i = 0; i < n - k - 1; i ++) cur = cur.next;tail.next = head;head = cur.next;cur.next = null;return head;}
}