每天一道leetcode61-旋轉鍊表

2021-03-02 程式設計師喬戈裡

考試結束,班級平均分只拿到了年級第二,班主任於是問道:大家都知道世界第一高峰珠穆朗瑪峰,有人知道世界第二高峰是什麼嗎?正當班主任要繼續發話,只聽到角落默默想起來一個聲音:」K2」

前言

2018.11.21號打卡
今天的題目leetcode26:
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/description/

昨天的題解題目

每天一道leetcode61. 旋轉鍊表
分類:雙指針
中文連結:
https://leetcode-cn.com/problems/rotate-list/description/
英文連結
https://leetcode.com/problems/rotate-list/description/

題目詳述

給定一個鍊表,旋轉鍊表,將鍊表每個節點向右移動 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

題目詳解

思路

首先遍歷鍊表計算鍊表的長度length,然後用k去對length取餘,餘數是A,A就是鍊表需要向右移動的位置,餘數是A也就是需要把鍊表末尾的A個節點移動到鍊表頭部;

這裡的話需要找到倒數第A個節點,也就是使用雙指針,一個fast一個slow,fast先走A步,然後fast與slow一起走,當fast走到鍊表的末尾(fast.next = null),那麼slow就走到了倒數第(A+1)個節點(這裡自己畫一個節點鍊表示意圖,比劃一下就知道!)

然後就是旋轉啦~,slow的下一個節點是旋轉後的頭結點,保存下來以後,注意把slow.next = null(因為slow是旋轉後的末尾節點),fast的節點需要進行連接head,因為旋轉了,fast.next = head;(這樣把前後兩部分鍊表拼接起來~)

代碼

1/**
2 * Definition for singly-linked list.
3 * public class ListNode {
4 *     int val;
5 *     ListNode next;
6 *     ListNode(int x) { val = x; }
7 * }
8 */
9class Solution {
10    public ListNode rotateRight(ListNode head, int k) {
11        if(head == null || head.next == null)
12            return head;
13        int length = 0;
14        ListNode temp = head;
15        while(temp != null)
16        {
17            length++;
18            temp = temp.next;
19        }
20        k = k % length;
21        if(k == 0)
22            return head;
23        ListNode fast = head;
24        ListNode slow = head;
25        for(int i=0;i<k;i++)
26            fast = fast.next;
27        while(fast.next != null)
28        {
29            fast = fast.next;
30            slow = slow.next;
31        }
32        ListNode resultHead = slow.next;
33        slow.next = null;
34        fast.next = head;
35        return resultHead;
36    }
37}

代碼講解

11-12 只有頭結點或者為空,直接返回

14-20行 計算鍊表長度,然後求餘,然後得出來需要旋轉多少個節點

21-22行 餘數為0,直接返回,不需要旋轉

25-26行 fast先走K步

27-31行 slow和fast一起走,直到fast走到最後一個節點,那麼slow就走到了倒數第K+1個節點了!

32-34行 進行旋轉,slow的下一個節點是旋轉後的頭結點,resultHead保存下來以後,注意把slow.next = null(因為slow是旋轉後的末尾節點),fast的節點需要進行連接head,因為旋轉了,fast這個節點到了前面了,fast.next = head;(這樣把前後兩部分鍊表拼接起來~)

結束語

2018.11.21號打卡

作者喬戈裡親歷2019秋招,哈工大計算機本碩,百度java工程師,歡迎大家關注我的微信公眾號:程式設計師喬戈裡,公眾號有3T編程資源,以及我和我朋友(百度C++工程師)在秋招期間整理的近200M的面試必考的java與C++面經,並有每天一道leetcode打卡群與技術交流群,歡迎關注。

幫戳文末的 獷高 相當於打賞2毛

相關焦點

  • 合併兩個有序鍊表 | Leetcode題解
    題目描述將兩個升序鍊表合併為一個新的升序鍊表並返回。新鍊表是通過拼接給定的兩個鍊表的所有節點組成的。 /problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/複雜度分析M、N 是兩條鍊表 l1、l2 的長度
  • Leetcode刷題-鍊表
    鍊表中倒數第k個節點難度:簡單輸入一個鍊表,輸出該鍊表中倒數第k個節點。為了符合大多數人的習慣,本題從1開始計數,即鍊表的尾節點是倒數第1個節點。例如,一個鍊表有6個節點,從頭節點開始,它們的值依次是1、2、3、4、5、6。這個鍊表的倒數第3個節點是值為4的節點。
  • Anki實戰-刷leetcode之「141-環形鍊表」
    有同學說自己刷leetcode的時候每次刷完就忘,忘了再刷。
  • LeetCode 例題精講 | 05 雙指針*鍊表問題:快慢指針
    最後,附上一道鍊表問題的綜合練習題:鍊表排序(LeetCode 148 - Sort List[8])。這道題中需要使用到鍊表處理的各種技巧,還需要針對鍊表的性質選擇合適的排序方法。可以說只要掌握了這道題,就算掌握了鍊表類問題了。鍊表排序也是微軟面試中某個面試官的「三板斧」之一,可以看出這道題的普適性。
  • ​LeetCode刷題實戰148:排序鍊表
    所以,為了提高大家的算法能力,這個公眾號後續每天帶大家做一道算法題,題目就從LeetCode上面選 !今天和大家聊的問題叫做 排序鍊表,我們先來看題面:https://leetcode-cn.com/problems/sort-list/Given the head of a linked list, return the list after sorting it in ascending order.
  • ​LeetCode刷題實戰138:複製帶隨機指針的鍊表
    所以,為了提高大家的算法能力,這個公眾號後續每天帶大家做一道算法題,題目就從LeetCode上面選 !今天和大家聊的問題叫做 複製帶隨機指針的鍊表,我們先來看題面:https://leetcode-cn.com/problems/copy-list-with-random-pointer/A linked list is given such that each node contains an additional random pointer which
  • LeetCode-21.Merge Two Sorted Lists | 合併兩個有序鍊表
    題解這道題是經典的考察鍊表的題目。解法一:遞歸•終止條件:兩條鍊表分別名為 l1 和 l2,當 l1 為空或 l2 為空時結束•返回值:每一層調用都返回排序好的鍊表頭•本級遞歸內容:如果 l1 的 val 值更小,則將 l1.next 與排序好的鍊表頭相接,l2 同理•O(m+n)O(m+n),mm 為 l1的長度,nn 為 l2 的長度//Go/** * Definition
  • [LeetCode] 1019. Next Greater Node In Linked List 鍊表中的下一個較大的結點
    這道題給了一個鍊表,讓找出每個結點值的下一個較大的結點值,跟之前的 Next Greater Element I,Next Greater Element II,和 Next Greater Element III 很類似,不同的是這裡不是數組,而是鍊表,就稍稍的增加了一些難度,因為鍊表無法直接根據下標訪問元素,在遍歷鍊表之前甚至不知道總共有多少個結點。
  • LeetCode 328. 奇偶鍊表 | Python
    奇偶鍊表題目來源:力扣(LeetCode)https://leetcode-cn.com/problems/odd-even-linked-list/ 題目 給定一個單鍊表,把所有的奇數節點和偶數節點分別排在一起。
  • ​LeetCode刷題實戰25:K 個一組翻轉鍊表
    所以,為了提高大家的算法能力,這個公眾號後續每天帶大家做一道算法題,題目就從LeetCode上面選 !今天和大家聊的問題叫做K 個一組翻轉鍊表,我們先來看題面:https://leetcode-cn.com/problems/reverse-nodes-in-k-groupGiven a linked list, reverse the nodes of a linked list k at a time and return its
  • 每天一道leetcode18-四數之和
    正當班主任要繼續發話,只聽到角落默默想起來一個聲音:」K2」前言 2018.11.20號打卡今天的題目leetcode61:https://leetcode-cn.com/problems/rotate-list/description/昨天的題解題目 每天一道leetcode18- 四數之和分類:雙指針
  • LeetCode-23.合併K個排序鍊表(Merge k Sorted Lists)
    合併K個升序鍊表合併 k 個排序鍊表,返回合併後的排序鍊表。請分析和描述算法的複雜度。示例:輸入:[ 1->4->5, 1->3->4, 2->6]輸出: 1->1->2->3->4->4->5->6來源:力扣(LeetCode)連結:https://leetcode-cn.com/problems/merge-k-sorted-lists
  • ​LeetCode刷題實戰23:合併K個升序鍊表
    所以,為了提高大家的算法能力,這個公眾號後續每天帶大家做一道算法題,題目就從LeetCode上面選 !今天和大家聊的問題叫做合併K個升序鍊表,我們先來看題面:https://leetcode-cn.com/problems/merge-k-sorted-lists/Given an array of linked-lists lists, each linked list is sorted in ascending order.Merge
  • LeetCode-25.K個一組翻轉鍊表(Reverse Nodes in k-Group)
    K個一組翻轉鍊表給你一個鍊表,每 k 個節點一組進行翻轉,請你返回翻轉後的鍊表。k 是一個正整數,它的值小於或等於鍊表的長度。如果節點總數不是 k 的整數倍,那麼請將最後剩餘的節點保持原有順序。示例:給你這個鍊表:1->2->3->4->5當 k = 2 時,應當返回: 2->1->4->3->5當 k = 3 時,應當返回: 3->2->1->4->5說明:你的算法只能使用常數的額外空間。
  • LeetCode 147 | 對鍊表進行插入排序
    題目描述對鍊表進行插入排序。
  • 每天學一道leetcode:152.乘積最大子序列
    前言面試各位同學大家好,歡迎閱讀小王同學的長篇連載文章之《每天學一道leetcode》。題是一道難度為middle(中等)的題目,這道題源自於小王同學之前講解過的題目每天學一道leetcode:53. 最大子序和。
  • 一次搞定面試中的鍊表問題
    之前寫過一篇關於鍊表的文章,今天補上一些leetcode上鍊表相關的題目,繼續匯總鍊表相關的問題,也希望可以為找工作的同學們提供一點幫助。(之前寫過一篇鍊表的, 面試常考的排序算法,這裡進一步擴展了一些更有難度的問題)下面的鍊表題包括(對應leetcode上有的,我把連結附在後面):單鍊表轉置兩兩交換鍊表中的節點每k個節點一組翻轉鍊表判斷鍊表是否有環求鍊表上倒數第K個節點找到環形鍊表的起始節點求環的長度
  • LeetCode鍊表合併題目解析
    leetcode鍊表合併相關題目:21_merge-two-sorted-lists1699_merge-in-between-linked-lists21_merge-two-sorted-lists1、題目描述將兩個升序鍊表合併為一個新的 升序 鍊表並返回。
  • 每天學一道leetcode:103. 二叉樹的鋸齒形層次遍歷
    前言歡迎閱讀小王同學的長篇連載文章之《每天學一道leetcode》。如果您從前做過這道題目,可以從小王同學的文章裡增強對該題目的記憶和印象,思考一下小王同學給出的思路和解法有沒有優化的空間。題目分析103題是leetcode中一道中等難度的題目,這道題目是二叉樹的層次遍歷的變形題。小王同學曾經分析過二叉樹的層次遍歷這道題目,地址在
  • 春節大禮包|刷題技巧+80道Leetcode
    為了跳槽,我前兩年的春節都是在刷題中度過的,目前為止刷了小四百道leetcode,也算是有一些經驗,今天就跟大家分享下學習方法和我總結的乾貨。從個人感覺來看,0到100道是最難的一道坎,如果去刷 Leetbook 的話,不知不覺就夠了。其次是100-300這個階段,要靠自己的自律去支撐,突破之後對每個知識點的套路就都了解了,再往後就是看各種刁鑽的思路。