💢歡迎來到張胤塵的技術站
💥技術如江河，匯聚眾志成。代碼似星辰，照亮行征程。開源精神長，傳承永不忘。攜手共前行，未來更輝煌💥

官方站點： 力扣 Leetcode

算法每日一練 (5)

旋轉鏈表

題目地址：旋轉鏈表

題目描述

給你一個鏈表的頭節點 head ，旋轉鏈表，將鏈表每個節點向右移動 k 個位置。

示例 1：

輸入：head = [1,2,3,4,5], k = 2
輸出：[4,5,1,2,3]

示例 2：

輸入：head = [0,1,2], k = 4
輸出：[2,0,1]

提示：

• 鏈表中節點的數目在范圍 [0, 500] 內
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

解題思路

• 首先考慮邊界條件，由題意可知當出現以下情況時，不需要進行任何處理，直接返回頭節點即可：
  • 當鏈表是空時；
  • 當鏈表中只有一個節點時；
  • 當旋轉次數是0時；
• 另外對于鏈表的旋轉，如果鏈表形成一個環（循環鏈表），在適當的位置（節點總數 - 移動的步數 k）斷開，那么斷開的位置就是鏈表的尾節點，新的頭節點就是尾節點的下一個節點。
• 首先借助輔助指針變量 t 在循環中計算鏈表節點的數量 cnt，此時當循環結束后，t 變量的位置來到了鏈表的尾節點。
• 根據之前的分析，t->next = head 將尾節點和頭節點相連后，形成一條循環鏈表。
• 接著判斷旋轉的次數，當經過 k 次旋轉后，如果節點的位置沒有發生任何變化，則不需要再進行處理，直接返回即可。其中 int n = k % cnt; 的 n == 0 時，表示位置未發生變化。
• 根據之前分析的結果，利用循環從鏈表當前頭節點開始移動，移動（頭節點移動鏈表節點總數 - 移動的步數 k）后到達新的尾節點位置。
• 那么新的尾節點的下一個節點就是新的頭節點。
• 最后返回頭節點即可。

解題代碼

c/c++

#include <vector>struct ListNode
{int val;ListNode *next;ListNode() : val(0), next(nullptr) {}ListNode(int x) : val(x), next(nullptr) {}ListNode(int x, ListNode *next) : val(x), next(next) {}
};class Solution
{
public:ListNode *rotateRight(ListNode *head, int k){if (!head || !head->next || k == 0)return head;int cnt = 1;ListNode *t = head;while (t->next){++cnt;t = t->next;}t->next = head;int n = k % cnt;if (n == 0){t->next = nullptr;return head;}ListNode *nTail = head;int setp = cnt - n - 1;while (setp){nTail = nTail->next;--setp;}head = nTail->next;nTail->next = nullptr;return head;}
};

golang

package maintype ListNode struct {Val  intNext *ListNode
}func rotateRight(head *ListNode, k int) *ListNode {if head == nil || head.Next == nil || k == 0 {return head}cnt := 1t := headfor t.Next != nil {cnt++t = t.Next}t.Next = headn := k % cntif n == 0 {t.Next = nilreturn head}setp := cnt - n - 1nTail := headfor setp != 0 {nTail = nTail.Nextsetp--}head = nTail.NextnTail.Next = nilreturn head
}

lua

local ListNode = {}function ListNode:new(val, next)local obj = {}setmetatable(obj, self)self.__index = selfobj.Val = val or 0obj.Next = next or nilreturn obj
endlocal function rotateRight(head, k)if head == nil or head.Next == nil or k == 0 thenreturn headendlocal cnt = 1local t = headwhile t.Next ~= nil docnt = cnt + 1t = t.Nextendt.Next = headlocal n = k % cntif n == 0 thent.Next = nilreturn headendlocal nTail = headlocal setp = cnt - n - 1while setp ~= 0 donTail = nTail.Nextsetp = setp - 1endhead = nTail.NextnTail.Next = nilreturn head
end

🌺🌺🌺撒花！

如果本文對你有幫助，就點關注或者留個👍
如果您有任何技術問題或者需要更多其他的內容，請隨時向我提問。