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