資訊專欄INFORMATION COLUMN
摘要：不過(guò)，由于可能大于鏈表的長(zhǎng)度，所以我們要先對(duì)取鏈表長(zhǎng)度的模。代碼計(jì)算鏈表長(zhǎng)度如果不旋轉(zhuǎn)或者原鏈表為空則直接返回讓快指針先走步找到新頭節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)將后半部分放到前面來(lái)
Rotate List
雙指針?lè)?/b> 復(fù)雜度Given a list, rotate the list to the right by k places, where k is non-negative.
For example: Given 1->2->3->4->5->NULL and k = 2, return 4->5->1->2->3->NULL.
時(shí)間 O(N) 空間 O(1)
思路旋轉(zhuǎn)鏈表的本質(zhì)，就是把鏈表的后半部分放到前面來(lái)，所以關(guān)鍵在于如何找鏈表后半部分的起始節(jié)點(diǎn)。實(shí)際上，我們用一個(gè)快指針先走k步，然后快慢指針同時(shí)走，這樣當(dāng)快指針到末尾時(shí)，慢指針就到鏈表后半部分的起始節(jié)點(diǎn)了。不過(guò)，由于k可能大于鏈表的長(zhǎng)度，所以我們要先對(duì)k取鏈表長(zhǎng)度的模。要計(jì)算鏈表長(zhǎng)度只要遍歷一遍鏈表就行了。
注意k取余后為0，或者原鏈表為空的情況下，都要直接返回原鏈表，不然將慢指針的下一個(gè)作為新鏈表頭會(huì)出錯(cuò)。
代碼public class Solution {
public ListNode rotateRight(ListNode head, int k) {
ListNode fast = head;
int length = 0;
// 計(jì)算鏈表長(zhǎng)度
while(fast != null){
length++;
fast = fast.next;
}
// 如果不旋轉(zhuǎn)或者原鏈表為空 則直接返回
if(head == null || k % length == 0){
return head;
}
fast = head;
// 讓快指針先走k步
for(int i = 0; i < k % length; i++){
fast = fast.next;
}
// 找到新頭節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)
ListNode slow = head;
while(fast.next != null){
fast = fast.next;
slow = slow.next;
}
// 將后半部分放到前面來(lái)
ListNode newHead = slow.next;
slow.next = null;
fast.next = head;
return newHead;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/64627.html
摘要：給定一個(gè)鏈表，旋轉(zhuǎn)鏈表，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng)個(gè)位置，其中是非負(fù)數(shù)。按上述思路解，與旋轉(zhuǎn)數(shù)組那道題大同小異，來(lái)介紹另一種很簡(jiǎn)單高效的方法。只需在第個(gè)節(jié)點(diǎn)之后切斷，首尾連接即可。另外可能大于鏈表長(zhǎng)度，應(yīng)當(dāng)做求余運(yùn)算。 ?給定一個(gè)鏈表，旋轉(zhuǎn)鏈表，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng) k 個(gè)位置，其中 k 是非負(fù)數(shù)。 Given a linked list, rotate the list to the ...
摘要：微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
摘要：有效三角形的個(gè)數(shù)雙指針最暴力的方法應(yīng)該是三重循環(huán)枚舉三個(gè)數(shù)字。總結(jié)本題和三數(shù)之和很像，都是三個(gè)數(shù)加和為某一個(gè)值。所以我們可以使用歸并排序來(lái)解決這個(gè)問(wèn)題。注意因?yàn)闅w并排序需要遞歸，所以空間復(fù)雜度為 ...
摘要：而后吾當(dāng)依除取余之法，化大為小，則指針不致于越界也。后欲尋右起第結(jié)點(diǎn)，令快指針先行數(shù)日，及至兩指針相距為，便吟鞭東指，與慢指針策馬共進(jìn)?？炻羔樢嘀褂谄渌?。舞動(dòng)長(zhǎng)劍，中宮直入，直取首級(jí)，而一掌劈空，已鴻飛冥冥。自此，一代天驕，霸業(yè)已成。 Problem Given a list, rotate the list to the right by k places, where k is...
摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...
閱讀 1812·2023-04-26 02:30
閱讀 1131·2021-11-10 11:36
閱讀 1482·2021-10-08 10:14
閱讀 3606·2021-09-28 09:35
閱讀 1618·2021-08-23 09:47
閱讀 2639·2019-08-30 15:56
閱讀 1547·2019-08-30 15:44
閱讀 1884·2019-08-30 13:59
