LeetCode 61：旋轉(zhuǎn)鏈表 Rotate List

Hwg 發(fā)布于2019-07-31 11:30 / 646人閱讀

摘要：給定一個鏈表，旋轉(zhuǎn)鏈表，將鏈表每個節(jié)點(diǎn)向右移動個位置，其中是非負(fù)數(shù)。按上述思路解，與旋轉(zhuǎn)數(shù)組那道題大同小異，來介紹另一種很簡單高效的方法。只需在第個節(jié)點(diǎn)之后切斷，首尾連接即可。另外可能大于鏈表長度，應(yīng)當(dāng)做求余運(yùn)算。

?給定一個鏈表，旋轉(zhuǎn)鏈表，將鏈表每個節(jié)點(diǎn)向右移動 k 個位置，其中 k 是非負(fù)數(shù)。

Given a linked list, rotate the list to the right by k places, where k is non-negative.

示例 1:

輸入: 1->2->3->4->5->NULL, k = 2
輸出: 4->5->1->2->3->NULL
解釋:
向右旋轉(zhuǎn) 1 步: 5->1->2->3->4->NULL
向右旋轉(zhuǎn) 2 步: 4->5->1->2->3->NULL

示例 2:

輸入: 0->1->2->NULL, k = 4
輸出: 2->0->1->NULL
解釋:
向右旋轉(zhuǎn) 1 步: 2->0->1->NULL
向右旋轉(zhuǎn) 2 步: 1->2->0->NULL
向右旋轉(zhuǎn) 3 步: 0->1->2->NULL
向右旋轉(zhuǎn) 4 步: 2->0->1->NULL

解題思路：

如果你看過上周的文章：LeetCode 189：旋轉(zhuǎn)數(shù)組，和本篇文章旋轉(zhuǎn)鏈表除了承載數(shù)據(jù)的結(jié)構(gòu)變了，其他都一樣，簡單說一下

不斷反轉(zhuǎn)特定長度數(shù)組：

輸入:1->2->3->4->5反轉(zhuǎn)整個數(shù)組: 5->4->3->2->1
拆分鏈表前k位為一段：5->4 , 3->2->1
反轉(zhuǎn)前k位：4->5
反轉(zhuǎn)剩余的:1->2->3
連接并輸出: 4->5->1->2->3

按照這個思路，只需三次反轉(zhuǎn)鏈表即可，而反轉(zhuǎn)鏈表我們已經(jīng)在文章 LeetCode 206：反轉(zhuǎn)鏈表中已經(jīng)詳細(xì)的介紹過了，用了迭代、遞歸兩種方法，所以按照上述解該題的方法也可以用兩種方法實現(xiàn)。

按上述思路解，與旋轉(zhuǎn)數(shù)組那道題大同小異，來介紹另一種很簡單高效的方法。

觀察輸入輸出：

輸入：1->2->3->4->5，k=2
輸出：4->5->1->2->3在節(jié)點(diǎn)3后切斷鏈表：1->2->3，4->5
將頭節(jié)點(diǎn)連接到尾節(jié)點(diǎn)：4->5->1->2->3
輸出：4->5->1->2->3

得益于鏈表的特性，明顯這種方式更簡單，而節(jié)點(diǎn)3的位置剛好就是 len-k (len為鏈表長度)。只需在第 len-k 個節(jié)點(diǎn)之后切斷，首尾連接即可。

另外 k 可能大于鏈表長度，應(yīng)當(dāng)做求余運(yùn)算 k=k%len 。考慮到切斷的節(jié)點(diǎn)位置可能是最后一個節(jié)點(diǎn)，或者是位置 0 (即頭節(jié)點(diǎn)前)，明顯不用做切斷節(jié)點(diǎn)，但是按上述操作就會出現(xiàn)指針溢出報錯，可以率先將首尾節(jié)點(diǎn)相連，組成環(huán)形鏈表。

Java：

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null || k == 0) return head;
        int len = 1;
        ListNode cur = head;
        while (cur.next != null) {//計算鏈表長度
            cur = cur.next;
            len++;
        }
        cur.next = head;
        int mod = len - k % len;//切斷節(jié)點(diǎn)的位置
        cur = head;
        while (--mod > 0) cur = cur.next;//找到切斷節(jié)點(diǎn)
        ListNode newHead = cur.next;//新鏈表頭節(jié)點(diǎn)
        cur.next = null;//切斷
        return newHead;
    }
}

Python3：

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next or not k: return head
        cur = head
        len = 1
        while cur.next:
            len += 1
            cur = cur.next
        cur.next = head
        cur = head
        mod = len - k % len
        while mod - 1 > 0:
            cur = cur.next
            mod -= 1
        newHead = cur.next
        cur.next = None
        return newHead

歡迎關(guān)注微.信公.眾號一起學(xué)習(xí)：愛寫B(tài)ug

GPU云服務(wù)器云服務(wù)器旋轉(zhuǎn)-rotate C語言數(shù)據(jù)結(jié)構(gòu)旋轉(zhuǎn)鏈表 Rotate LeetCode

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/45239.html

發(fā)表評論

登陸后可評論

0條評論

Hwg

男|高級講師

我要關(guān)注我要私信

TA的文章

tensorflow對應(yīng)的cuda版本

閱讀 2025·2023-04-25 14:50
刷題日記Day2 | 構(gòu)造二叉樹

閱讀 2907·2021-11-17 09:33
Safari的CSS HACK方法

閱讀 2611·2019-08-30 13:07
前端每日實戰(zhàn)：154# 視頻演示如何創(chuàng)作一個眼冒金星的動畫效果

閱讀 2838·2019-08-29 16:57
IPhoneX網(wǎng)頁布局簡介

閱讀 908·2019-08-29 15:26
js中的0就是false，非0就是true。

閱讀 3540·2019-08-29 13:08
前端之CSS基礎(chǔ)學(xué)習(xí)

閱讀 1990·2019-08-29 12:32
9、 TypeScript 之函數(shù)返回值類型

閱讀 3383·2019-08-26 13:57

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

LeetCode 61：旋轉(zhuǎn)鏈表 Rotate List

相關(guān)文章

**[Leetcode] Rotate List 旋轉(zhuǎn)鏈表**