每天一道leetcode61-旋轉鏈表
- 2019 年 10 月 4 日
- 筆記
昨天的題解
題目
每天一道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;(這樣把前後兩部分鏈表拼接起來~）
程式碼
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode rotateRight(ListNode head, int k) { if(head == null || head.next == null) return head; int length = 0; ListNode temp = head; while(temp != null) { length++; temp = temp.next; } k = k % length; if(k == 0) return head; ListNode fast = head; ListNode slow = head; for(int i=0;i<k;i++) fast = fast.next; while(fast.next != null) { fast = fast.next; slow = slow.next; } ListNode resultHead = slow.next; slow.next = null; fast.next = head; return resultHead; } }
程式碼講解
- 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;(這樣把前後兩部分鏈表拼接起來~）
