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é)點欣硼,直接斷鏈返回就可以了。