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

imtianx 發(fā)布于2019-07-25 14:27 / 2746人閱讀

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

作者: 碼蹄疾
畢業(yè)于哈爾濱工業(yè)大學(xué)。 小米廣告第三代廣告引擎的設(shè)計者、開發(fā)者；
負責(zé)小米應(yīng)用商店、日歷、開屏廣告業(yè)務(wù)線研發(fā)；
主導(dǎo)小米廣告引擎多個模塊重構(gòu)；
關(guān)注推薦、搜索、廣告領(lǐng)域相關(guān)知識;

給定一個鏈表，旋轉(zhuǎn)鏈表，將鏈表每個節(jié)點向右移動 k 個位置，其中 k 是非負數(shù)。

示例 1:

輸入: 1->2->3->4->5->NULL, k = 2
輸出: 4->5->1->2->3->NULL
解釋:
向右旋轉(zhuǎn) 1 步: 5->1->2->3->4->NULL
向右旋轉(zhuǎn) 2 步: 4->5->1->2->3->NULL

示例 2:

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

題解

昨晚吃火鍋吃撐了回來這道題，還算順利~~
鏈表的題目,其實就是在考指針交換,這個題目先讓鏈表連成一個環(huán)，然后再切開就可以完成了。

python版本

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None


class Solution(object):
    def rotateRight(self, head, k):
        """
        :type head: ListNode
        :type k: int
        :rtype: ListNode
        """
        if head is None or head.next is None:
            return head
        # 鏈表的節(jié)點個數(shù)
        count = 1
        cur = head
        while cur.next:
            count += 1
            cur = cur.next
        # 如果恰好走了一個環(huán),就直接返回
        k = k % count
        if k == 0:
            return head
        cur.next = head
        dummy = ListNode(-1)
        dummy.next = head
        prev = dummy
        # 需要走count-k個,然后把鏈表切斷
        for _ in range(count - k):
            prev = prev.next
        # 重新組成新的鏈表
        cur = prev.next
        new_head = cur
        
        prev.next = None

        return new_head

java版本

public class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (head == null || head.next == null) {
            return head;
        }

        int count = 1;
        ListNode cur = head;
        while (cur.next != null) {
            count++;
            cur = cur.next;
        }
        k = k % count;
        if (k == 0) {
            return head;
        }
        cur.next = head;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode prev = dummy;
        for (int i = 0; i < count - k; i++) {
            prev = prev.next;
        }
        cur = prev.next;
        prev.next = null;
        return cur;
    }
}

熱門閱讀

【Leetcode】60. 第k個排列

技術(shù)文章匯總

云服務(wù)器 GPU云服務(wù)器 C語言數(shù)據(jù)結(jié)構(gòu)旋轉(zhuǎn)鏈表 LeetCode 61vps 61cdn

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

轉(zhuǎn)載請注明本文地址：http://specialneedsforspecialkids.com/yun/40118.html

發(fā)表評論

登陸后可評論

0條評論

imtianx

男|高級講師

我要關(guān)注我要私信

TA的文章

六一云：美國G口/香港CTG/美國T級超防云/湖北高防云服務(wù)器物理機促銷活動

閱讀 3782·2021-09-23 11:32
Quartus II 軟件和 DE2-115 開發(fā)板使用入門

閱讀 2451·2021-09-06 15:01
盤點騰訊云服務(wù)器優(yōu)惠活動及新老用戶優(yōu)惠折扣「2021.8」

閱讀 1616·2021-08-18 10:24
更懂在線互動課堂，UCloud優(yōu)刻得推出URTC實時音視頻

閱讀 3450·2019-12-27 11:44
怎樣才能在WEB前端、HTML5開發(fā)的路上，越走越遠，越笑越好？！

閱讀 3605·2019-08-30 15:52
整理1

閱讀 2512·2019-08-30 11:11
寫一個菜鳥裹裹小程序吧

閱讀 671·2019-08-29 17:27
web 移動端橫向滾動的阻尼感很強，滑動不靈敏

閱讀 600·2019-08-29 16:22

国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺、長期優(yōu)惠，快來選購！

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

相關(guān)文章