【Leetcode】61.旋轉鏈表

Jeffrrey 發布于2019-08-19 11:06 / 3431人閱讀

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

作者: 碼蹄疾
畢業于哈爾濱工業大學。 小米廣告第三代廣告引擎的設計者、開發者；
負責小米應用商店、日歷、開屏廣告業務線研發；
主導小米廣告引擎多個模塊重構；
關注推薦、搜索、廣告領域相關知識;

給定一個鏈表，旋轉鏈表，將鏈表每個節點向右移動 k 個位置，其中 k 是非負數。

示例 1:

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

示例 2:

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

題解

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

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
        # 鏈表的節點個數
        count = 1
        cur = head
        while cur.next:
            count += 1
            cur = cur.next
        # 如果恰好走了一個環,就直接返回
        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個排列

技術文章匯總

云服務器 GPU云服務器 C語言數據結構旋轉鏈表 LeetCode 61vps 61cdn

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

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

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

imtianx 2019-07-25 14:27 評論0 收藏0
【Leetcode】61.旋轉鏈表

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

xushaojieaaa 2019-07-30 17:44 評論0 收藏0
6-9月技術文章匯總

摘要：分布式的管理和當我在談論架構時我在談啥狀態碼詳解無狀態協議和請求支持哪些方法分層協議棧有哪些數據結構運用場景說說你常用的命令為什么要有包裝類面向對象的特征是啥是啥有什么好處系統設計工程在線診斷系統設計與實現索引背后的數據結構及算法原理軟技能 HTTP 【HTTP】分布式session的管理【HTTP】Cookie和Session 【HTTP】當我在談論RestFul架構時我在談啥？...

miya 2019-07-30 18:03 評論0 收藏0