[Leetcode] Rotate List 旋轉鏈表

Yu_Huang 發(fā)布于2019-08-14 12:40 / 3518人閱讀

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

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)

思路

旋轉鏈表的本質(zhì)，就是把鏈表的后半部分放到前面來，所以關鍵在于如何找鏈表后半部分的起始節(jié)點。實際上，我們用一個快指針先走k步，然后快慢指針同時走，這樣當快指針到末尾時，慢指針就到鏈表后半部分的起始節(jié)點了。不過，由于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;
        } 
        // 找到新頭節(jié)點的前一個節(jié)點
        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語言數(shù)據(jù)結構旋轉鏈表 Rotate LeetCode

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

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

LeetCode 61：旋轉鏈表 Rotate List

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

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

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數(shù)據(jù)結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內(nèi)容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權之外的使用權限可以從處獲得。 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】

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

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

摘要：而后吾當依除取余之法，化大為小，則指針不致于越界也。后欲尋右起第結點，令快指針先行數(shù)日，及至兩指針相距為，便吟鞭東指，與慢指針策馬共進?？炻羔樢嘀褂谄渌伞Ｎ鑴娱L劍，中宮直入，直取首級，而一掌劈空，已鴻飛冥冥。自此，一代天驕，霸業(yè)已成。 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 題攻略）

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

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