https://leetcode-cn.com/problems/rotate-list/
準(zhǔn)備工作：
本題用到了一個思想峰髓，找到鏈表倒數(shù)第K個位置的節(jié)點
使用快慢指針：
ListNode slow = head, fast = head;
while (k-- > 0) fast = fast.next; // 這里會執(zhí)行 K 次宇攻， 不確定也可以用 for-loop
while (fast != null) { // 這里的判斷條件會讓 fast 走到最后的null
fast = fast.next;
slow = slow.next;
}
- 快慢指針指向頭，然后快指針先走K步恍风，這樣快慢指針間距就是K。然后快慢指針一起走术健，當(dāng)快指針走到尾節(jié)點時击蹲，慢指針?biāo)谖恢镁褪擎湵淼箶?shù)第 K 位置。
鏈表聲明：
class ListNode {
int val;
ListNode next;
ListNode() {
}
ListNode(int val) {
this.val = val;
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
解法一：快慢指針
- 雖然題目說的是旋轉(zhuǎn)鏈表铁瞒，但其實找到旋轉(zhuǎn)后的鏈表的新頭節(jié)點（倒數(shù)第 K 個位置）就可以了
- 這里要注意，題目給的 K 可能會超過鏈表的長度桅滋，也是官方設(shè)下的陷阱慧耍。所以一會要處理這個K
- 并且如果 K 是鏈表長度的整數(shù)倍，則翻轉(zhuǎn)的結(jié)果與原鏈表沒區(qū)別丐谋，直接返回芍碧。
public class Solution {
// slow-fast two pointer to find k-th from the bottom
public ListNode rotateRight(ListNode head, int k) {
if (head == null || k == 0) return head;
// judge k whether an integer multiple
int sum = 0; // length of the List
ListNode p = head;
while (p != null) {
p = p.next;
sum++;
}
k %= sum;
if (k == 0) return head;
ListNode slow = head, fast = head;
while (k-- > 0) fast = fast.next;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
ListNode newHead = slow.next;
slow.next = null;
fast.next = head; // location of fast pointer is at last of List
return newHead;
}
}
-
k %= sum;是剛才說的處理K。也是實際上鏈表需要旋轉(zhuǎn)的次數(shù)号俐。 -
while (fast.next != null)這里跟上面的準(zhǔn)備工作里的找到倒數(shù)第K個節(jié)點不同泌豆，區(qū)別在于判斷條件是fast.next。因為本題找到新頭節(jié)點后吏饿，要讓鏈表末尾節(jié)點連接到老頭節(jié)點踪危，然后讓新頭節(jié)點前的節(jié)點斷鏈。所以實際上處理的是：倒數(shù)第K個節(jié)點的前一個節(jié)點猪落。
解法二：閉環(huán)
- 官方解法贞远，先把鏈表閉環(huán)，然后找到倒數(shù)第K個位置作為新頭節(jié)點笨忌，同理兴革。
public class Solution {
// closed cycle and find k-th from the bottom
public ListNode rotateRight(ListNode head, int k) {
if (head == null || k == 0) return head;
// judge k whether an integer multiple
int sum = 1;
ListNode p = head;
// judging condition is p.next in order to move p to the last node
while (p.next != null) {
p = p.next;
sum++;
}
k %= sum;
if (k == 0) return head;
// closed cycle
p.next = head;
k = sum - k - 1;
while (k-- > 0) head = head.next;
ListNode newHead = head.next;
head.next = null;
return newHead;
}
}
- 涉及到幾個細(xì)節(jié)：
- 可以在統(tǒng)計鏈表長度的同時找到末尾節(jié)點，后面末尾節(jié)點連接到頭節(jié)點形成閉環(huán)操作蜜唾，復(fù)用指針p杂曲。所以這里統(tǒng)計長度又不同于解法一，sum初始化為1袁余，while-loop判斷對象為p.next擎勘，因為不能讓p為null，后面會NPE颖榜。
- 處理完K之后棚饵，在閉環(huán)之后開始找到真正的位置，即
sum - k - 1掩完，-1 的目的同上噪漾，新頭節(jié)點的前一個節(jié)點。 - 因為閉環(huán)的關(guān)系且蓬，所以不用特意去操作尾節(jié)點連到老頭節(jié)點欣硼，直接斷鏈返回就可以了。
