LeetCode 61：旋轉鏈表 Rotate List

Hwg 發布于2019-07-31 11:30 / 651人閱讀

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

?給定一個鏈表，旋轉鏈表，將鏈表每個節點向右移動 k 個位置，其中 k 是非負數。

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
解釋:
向右旋轉 1 步: 5->1->2->3->4->NULL
向右旋轉 2 步: 4->5->1->2->3->NULL

示例 2:

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

解題思路：

如果你看過上周的文章：LeetCode 189：旋轉數組，和本篇文章旋轉鏈表除了承載數據的結構變了，其他都一樣，簡單說一下

不斷反轉特定長度數組：

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

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

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

觀察輸入輸出：

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

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

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

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;//切斷節點的位置
        cur = head;
        while (--mod > 0) cur = cur.next;//找到切斷節點
        ListNode newHead = cur.next;//新鏈表頭節點
        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

歡迎關注微.信公.眾號一起學習：愛寫Bug

云服務器 GPU云服務器旋轉-rotate C語言數據結構旋轉鏈表 Rotate LeetCode

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/45239.html

[Leetcode] Rotate List 旋轉鏈表

摘要：不過，由于可能大于鏈表的長度，所以我們要先對取鏈表長度的模。代碼計算鏈表長度如果不旋轉或者原鏈表為空則直接返回讓快指針先走步找到新頭節點的前一個節點將后半部分放到前面來 Rotate List Given a list, rotate the list to the right by k places, where k is non-negative. For example: Gi...

Yu_Huang 2019-08-14 12:40 評論0 收藏0
【Leetcode】61.旋轉鏈表

摘要：小米廣告第三代廣告引擎的設計者開發者負責小米應用商店日歷開屏廣告業務線研發主導小米廣告引擎多個模塊重構關注推薦搜索廣告領域相關知識給定一個鏈表，旋轉鏈表，將鏈表每個節點向右移動個位置，其中是非負數。作者: 碼蹄疾畢業于哈爾濱工業大學。小米廣告第三代廣告引擎的設計者、開發者；負責小米應用商店、日歷、開屏廣告業務線研發；主導小米廣告引擎多個模塊重構；關注推薦、搜索、廣告領域相關知識; ...

Jeffrrey 2019-08-19 11:06 評論0 收藏0
【Leetcode】61.旋轉鏈表

摘要：小米廣告第三代廣告引擎的設計者開發者負責小米應用商店日歷開屏廣告業務線研發主導小米廣告引擎多個模塊重構關注推薦搜索廣告領域相關知識給定一個鏈表，旋轉鏈表，將鏈表每個節點向右移動個位置，其中是非負數。作者: 碼蹄疾畢業于哈爾濱工業大學。小米廣告第三代廣告引擎的設計者、開發者；負責小米應用商店、日歷、開屏廣告業務線研發；主導小米廣告引擎多個模塊重構；關注推薦、搜索、廣告領域相關知識; ...

imtianx 2019-07-25 14:27 評論0 收藏0
【Leetcode】61.旋轉鏈表

摘要：小米廣告第三代廣告引擎的設計者開發者負責小米應用商店日歷開屏廣告業務線研發主導小米廣告引擎多個模塊重構關注推薦搜索廣告領域相關知識給定一個鏈表，旋轉鏈表，將鏈表每個節點向右移動個位置，其中是非負數。作者: 碼蹄疾畢業于哈爾濱工業大學。小米廣告第三代廣告引擎的設計者、開發者；負責小米應用商店、日歷、開屏廣告業務線研發；主導小米廣告引擎多個模塊重構；關注推薦、搜索、廣告領域相關知識; ...

xushaojieaaa 2019-07-30 17:44 評論0 收藏0