旋轉(zhuǎn)鏈表


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é)點欣硼,直接斷鏈返回就可以了。
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
禁止轉(zhuǎn)載恶阴,如需轉(zhuǎn)載請通過簡信或評論聯(lián)系作者诈胜。
  • 序言:七十年代末,一起剝皮案震驚了整個濱河市冯事,隨后出現(xiàn)的幾起案子焦匈,更是在濱河造成了極大的恐慌,老刑警劉巖昵仅,帶你破解...
    沈念sama閱讀 222,807評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件缓熟,死亡現(xiàn)場離奇詭異,居然都是意外死亡摔笤,警方通過查閱死者的電腦和手機够滑,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來籍茧,“玉大人版述,你說我怎么就攤上這事∧耄” “怎么了渴析?”我有些...
    開封第一講書人閱讀 169,589評論 0 363
  • 文/不壞的土叔 我叫張陵,是天一觀的道長吮龄。 經(jīng)常有香客問我俭茧,道長,這世上最難降的妖魔是什么漓帚? 我笑而不...
    開封第一講書人閱讀 60,188評論 1 300
  • 正文 為了忘掉前任母债,我火速辦了婚禮,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘毡们。我一直安慰自己迅皇,他們只是感情好,可當(dāng)我...
    茶點故事閱讀 69,185評論 6 398
  • 文/花漫 我一把揭開白布衙熔。 她就那樣靜靜地躺著登颓,像睡著了一般。 火紅的嫁衣襯著肌膚如雪红氯。 梳的紋絲不亂的頭發(fā)上框咙,一...
    開封第一講書人閱讀 52,785評論 1 314
  • 那天,我揣著相機與錄音痢甘,去河邊找鬼喇嘱。 笑死,一個胖子當(dāng)著我的面吹牛塞栅,可吹牛的內(nèi)容都是我干的者铜。 我是一名探鬼主播,決...
    沈念sama閱讀 41,220評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼构蹬,長吁一口氣:“原來是場噩夢啊……” “哼王暗!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起庄敛,我...
    開封第一講書人閱讀 40,167評論 0 277
  • 序言:老撾萬榮一對情侶失蹤俗壹,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后藻烤,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體绷雏,經(jīng)...
    沈念sama閱讀 46,698評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 38,767評論 3 343
  • 正文 我和宋清朗相戀三年怖亭,在試婚紗的時候發(fā)現(xiàn)自己被綠了涎显。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 40,912評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡兴猩,死狀恐怖期吓,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情倾芝,我是刑警寧澤讨勤,帶...
    沈念sama閱讀 36,572評論 5 351
  • 正文 年R本政府宣布,位于F島的核電站晨另,受9級特大地震影響潭千,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜借尿,卻給世界環(huán)境...
    茶點故事閱讀 42,254評論 3 336
  • 文/蒙蒙 一刨晴、第九天 我趴在偏房一處隱蔽的房頂上張望屉来。 院中可真熱鬧,春花似錦狈癞、人聲如沸茄靠。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽嘹黔。三九已至,卻和暖如春莫瞬,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背郭蕉。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評論 1 274
  • 我被黑心中介騙來泰國打工疼邀, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留,地道東北人召锈。 一個月前我還...
    沈念sama閱讀 49,359評論 3 379
  • 正文 我出身青樓旁振,卻偏偏與公主長得像,于是被迫代替她去往敵國和親涨岁。 傳聞我的和親對象是個殘疾皇子拐袜,可洞房花燭夜當(dāng)晚...
    茶點故事閱讀 45,922評論 2 361