[Leetcode] Rotate List 旋轉鏈表

Yu_Huang 發布于2019-08-14 12:40 / 3511人閱讀

摘要：不過，由于可能大于鏈表的長度，所以我們要先對取鏈表長度的模。代碼計算鏈表長度如果不旋轉或者原鏈表為空則直接返回讓快指針先走步找到新頭節點的前一個節點將后半部分放到前面來

Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.
For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.

雙指針法 復雜度

時間 O(N) 空間 O(1)

思路

旋轉鏈表的本質，就是把鏈表的后半部分放到前面來，所以關鍵在于如何找鏈表后半部分的起始節點。實際上，我們用一個快指針先走k步，然后快慢指針同時走，這樣當快指針到末尾時，慢指針就到鏈表后半部分的起始節點了。不過，由于k可能大于鏈表的長度，所以我們要先對k取鏈表長度的模。要計算鏈表長度只要遍歷一遍鏈表就行了。

注意

k取余后為0，或者原鏈表為空的情況下，都要直接返回原鏈表，不然將慢指針的下一個作為新鏈表頭會出錯。

代碼

public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        ListNode fast = head;
        int length = 0;
        // 計算鏈表長度
        while(fast != null){
            length++;
            fast = fast.next;
        }
        // 如果不旋轉或者原鏈表為空 則直接返回
        if(head == null || k % length == 0){
            return head;
        }
        fast = head;
        // 讓快指針先走k步
        for(int i = 0; i < k % length; i++){
            fast = fast.next;
        } 
        // 找到新頭節點的前一個節點
        ListNode slow = head;
        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        // 將后半部分放到前面來
        ListNode newHead = slow.next;
        slow.next = null;
        fast.next = head;
        return newHead;
    }
}

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

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

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

LeetCode 61：旋轉鏈表 Rotate List

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

Hwg 2019-07-31 11:30 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
LeetCode 精選TOP面試題【51 ~ 100】

摘要：有效三角形的個數雙指針最暴力的方法應該是三重循環枚舉三個數字。總結本題和三數之和很像，都是三個數加和為某一個值。所以我們可以使用歸并排序來解決這個問題。注意因為歸并排序需要遞歸，所以空間復雜度為 ...

Clect 2021-11-15 11:38 評論0 收藏0
[LintCode/LeetCode] Rotate List

摘要：而后吾當依除取余之法，化大為小，則指針不致于越界也。后欲尋右起第結點，令快指針先行數日，及至兩指針相距為，便吟鞭東指，與慢指針策馬共進。快慢指針亦止于其所焉。舞動長劍，中宮直入，直取首級，而一掌劈空，已鴻飛冥冥。自此，一代天驕，霸業已成。 Problem Given a list, rotate the list to the right by k places, where k is...

Blackjun 2019-08-14 15:22 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經到題，所以后面會調整自己，在刷算法與數據結構的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚有什么區別...

tain335 2019-08-26 10:28 評論0 收藏0