描述
在一個(gè)單鏈表中轴术，在第k個(gè)位置向右旋轉(zhuǎn)單鏈表，k是一個(gè)非負(fù)值盖袭。
輸入：
? 1->2->3->4->5->nullptr彼宠， k=2
輸出
? 4->5->1->2->3->nullptr
分析
遍歷鏈表凭峡，計(jì)算出鏈表的長(zhǎng)度，將鏈表的尾結(jié)點(diǎn)連接到頭節(jié)點(diǎn)形成一個(gè)環(huán)鏈表摧冀，再往后遍歷len-k個(gè)節(jié)點(diǎn)系宫，從此將鏈表斷開(kāi)即可扩借。需要兼容k超出鏈表長(zhǎng)度時(shí)的情況往枷。
實(shí)現(xiàn)
ListNode *rotateList(ListNode *head, int k)
{
int len = 1;
// 計(jì)算長(zhǎng)度
ListNode *cur = head;
while (cur->next) {
++len;
cur = cur->next;
}
// 兼容k
k = len - k%len;
//形成環(huán)鏈表
cur->next = head;
// 再向前走k個(gè)節(jié)點(diǎn)
for(int i=0; i<k; i++) {
cur = cur->next;
}
head = cur->next;
cur->next = nullptr;
return head;
}
時(shí)間復(fù)雜度O(n)凄杯，空間復(fù)雜度為O(1)戒突。
