成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

leetcode61 Rotate List

nodejh / 2500人閱讀

摘要：根據(jù)列表的長(zhǎng)度，計(jì)算，也就是最短等價(jià)移動(dòng)次數(shù)。之后利用雙指針，保證頭指針和尾指針之間的距離始終為，從而找到右邊第個(gè)節(jié)點(diǎn)。這時(shí)候還計(jì)算數(shù)組的長(zhǎng)度的話，反而降低了性能。

題目要求 
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.

其實(shí)這題的描述有些不妥當(dāng)，確切的說是將最右側(cè)的節(jié)點(diǎn)依次移到最左側(cè)作為頭結(jié)點(diǎn)，一直移動(dòng)到右側(cè)第k個(gè)節(jié)點(diǎn)后結(jié)束。
還是以1->2->3->4->5->NULL為例
k=1 結(jié)果為：5->1->2->3->4->NULL
k=2 結(jié)果為：4->5->1->2->3->NULL
k=3 結(jié)果為：3->4->5->1->2->NULL
k=4 結(jié)果為：2->3->4->5->1->NULL
k=5 結(jié)果為：1->2->3->4->5->NULL
k=6 結(jié)果為：5->1->2->3->4->NULL

換句話說 當(dāng)k的值超過了list的長(zhǎng)度len的時(shí)候，移動(dòng)k次等價(jià)于移動(dòng)k%len次

思路一：計(jì)算出list長(zhǎng)度

即通過一次遍歷，找到列表的末節(jié)點(diǎn)同時(shí)，計(jì)算出列表的長(zhǎng)度。根據(jù)列表的長(zhǎng)度，計(jì)算k%len，也就是最短等價(jià)移動(dòng)次數(shù)。之后利用雙指針，保證頭指針和尾指針之間的距離始終為k，從而找到右邊第k個(gè)節(jié)點(diǎn)。

    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;
           
    }
思路二：簡(jiǎn)單優(yōu)化

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

    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);
        } 
    }


想要了解更多開發(fā)技術(shù)，面試教程以及互聯(lián)網(wǎng)公司內(nèi)推，歡迎關(guān)注我的微信公眾號(hào)！將會(huì)不定期的發(fā)放福利哦~

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/70111.html

相關(guān)文章

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

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

    Hwg 評(píng)論0 收藏0

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

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

    Yu_Huang 評(píng)論0 收藏0

  • [LintCode/LeetCode] Rotate List

    摘要：而后吾當(dāng)依除取余之法，化大為小，則指針不致于越界也。后欲尋右起第結(jié)點(diǎn)，令快指針先行數(shù)日，及至兩指針相距為，便吟鞭東指，與慢指針策馬共進(jìn)?？炻羔樢嘀褂谄渌伞Ｎ鑴?dòng)長(zhǎng)劍，中宮直入，直取首級(jí)，而一掌劈空，已鴻飛冥冥。自此，一代天驕，霸業(yè)已成。 Problem Given a list, rotate the list to the right by k places, where k is...

    Blackjun 評(píng)論0 收藏0

  • 【Leetcode】61.旋轉(zhuǎn)鏈表

    摘要：小米廣告第三代廣告引擎的設(shè)計(jì)者開發(fā)者負(fù)責(zé)小米應(yīng)用商店日歷開屏廣告業(yè)務(wù)線研發(fā)主導(dǎo)小米廣告引擎多個(gè)模塊重構(gòu)關(guān)注推薦搜索廣告領(lǐng)域相關(guān)知識(shí)給定一個(gè)鏈表，旋轉(zhuǎn)鏈表，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng)個(gè)位置，其中是非負(fù)數(shù)。 作者: 碼蹄疾畢業(yè)于哈爾濱工業(yè)大學(xué)。 小米廣告第三代廣告引擎的設(shè)計(jì)者、開發(fā)者；負(fù)責(zé)小米應(yīng)用商店、日歷、開屏廣告業(yè)務(wù)線研發(fā)；主導(dǎo)小米廣告引擎多個(gè)模塊重構(gòu)；關(guān)注推薦、搜索、廣告領(lǐng)域相關(guān)知識(shí); ...

    Jeffrrey 評(píng)論0 收藏0

  • 【Leetcode】61.旋轉(zhuǎn)鏈表

    摘要：小米廣告第三代廣告引擎的設(shè)計(jì)者開發(fā)者負(fù)責(zé)小米應(yīng)用商店日歷開屏廣告業(yè)務(wù)線研發(fā)主導(dǎo)小米廣告引擎多個(gè)模塊重構(gòu)關(guān)注推薦搜索廣告領(lǐng)域相關(guān)知識(shí)給定一個(gè)鏈表，旋轉(zhuǎn)鏈表，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng)個(gè)位置，其中是非負(fù)數(shù)。 作者: 碼蹄疾畢業(yè)于哈爾濱工業(yè)大學(xué)。 小米廣告第三代廣告引擎的設(shè)計(jì)者、開發(fā)者；負(fù)責(zé)小米應(yīng)用商店、日歷、開屏廣告業(yè)務(wù)線研發(fā)；主導(dǎo)小米廣告引擎多個(gè)模塊重構(gòu)；關(guān)注推薦、搜索、廣告領(lǐng)域相關(guān)知識(shí); ...

    imtianx 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<