leetcode61 Rotate List

nodejh 發布于2019-08-16 10:36 / 2495人閱讀

摘要：根據列表的長度，計算，也就是最短等價移動次數。之后利用雙指針，保證頭指針和尾指針之間的距離始終為，從而找到右邊第個節點。這時候還計算數組的長度的話，反而降低了性能。

題目要求

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.

其實這題的描述有些不妥當，確切的說是將最右側的節點依次移到最左側作為頭結點，一直移動到右側第k個節點后結束。
還是以1->2->3->4->5->NULL為例
k=1 結果為：5->1->2->3->4->NULL
k=2 結果為：4->5->1->2->3->NULL
k=3 結果為：3->4->5->1->2->NULL
k=4 結果為：2->3->4->5->1->NULL
k=5 結果為：1->2->3->4->5->NULL
k=6 結果為：5->1->2->3->4->NULL

換句話說當k的值超過了list的長度len的時候，移動k次等價于移動k%len次

思路一：計算出list長度

即通過一次遍歷，找到列表的末節點同時，計算出列表的長度。根據列表的長度，計算k%len，也就是最短等價移動次數。之后利用雙指針，保證頭指針和尾指針之間的距離始終為k，從而找到右邊第k個節點。

    public ListNode rotateRight2(ListNode head, int k) {
        if(k==0 || head==null)
            return head;
        
        //get list length and last node
        ListNode last = head;
        int len = 1;
        while(last.next != null){
            last = last.next;
            len++;
        }
        
        
        k = k%len;
        if(k==0)
            return head;
        ListNode start = new ListNode(0);
        start.next = head;
        int count = len-k;
        while(count > 0){
            start = start.next;
            count--;
        }
        
        last.next = head;
        head = start.next;
        start.next = null;
        
        return head;
           
    }

思路二：簡單優化

其實在某些情況下，k的值并不一定比數組的長度大。這時候還計算數組的長度的話，反而降低了性能。這個時候，可以將遍歷的過程和頭指針的移動結合起來。如果頭指針移動到結尾而k并不是等于0，則可以得知k大于列表長度，同時這個過程還可以得出列表的長度。如果k等于0時，頭指針未移動到末尾，則可以繼續頭指針和尾指針的同時移動，知道頭指針到達數組的最后一個元素。
代碼如下：

    public ListNode rotateRight(ListNode head, int k) {
        if(head == null){
            return null;
        }
        ListNode firstPointer = head;
        int length = 0;
        while(firstPointer!= null && k > 0){
            k--;
            firstPointer = firstPointer.next;
            length++;
        }
        if(k == 0){
            if(firstPointer == null){
                return head;
            }
            ListNode secondPointer = head;
            while(firstPointer != null && firstPointer.next!=null){
                secondPointer = secondPointer.next;
                firstPointer = firstPointer.next;
            }
            firstPointer.next = head;
            ListNode result = secondPointer.next;
            secondPointer.next = null;
            return result;
        }else{
            return rotateRight(head, k%length);
        } 
    }

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 Rotate 旋轉-rotate Leetcod LeetCode

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/70111.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] 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
[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】61.旋轉鏈表

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

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

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

imtianx 2019-07-25 14:27 評論0 收藏0