目錄
- 1、題目
- 2、思路
- 3、c++代碼
- 4、java代碼
1、題目
給你一個鏈表的頭節點 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 <= 1000 <= k <= 2 * 109
2、思路
(模擬) O ( n ) O(n) O(n)
給你一個鏈表的頭節點 head ，然后將鏈表每個節點向右移動 k 個位置，
樣例：
如樣例所示，head = [1,2,3,4,5]，k = 2，我們輸出[4,5,1,2,3]，下面來講解模擬的做法，
假設鏈表的長度為n，為了將鏈表每個節點向右移動 k 個位置，我們只需要將鏈表的后 k % n個節點移動到鏈表的最前面，然后將鏈表的后k % n個節點和前 n - k個節點連接到一塊即可，
具體程序如下：
1、首先遍歷整個鏈表，求出鏈表的長度n，并找出鏈表的尾節點tail，
2、由于k可能很大，所以我們令 k = k % n，然后再次從頭節點head開始遍歷，找到第n - k個節點p，那么1 ~ p是鏈表的前 n - k個節點，p+1 ~ n是鏈表的后k個節點，
3、接下來就是依次執行tail->next = head，head = p->next，p->next = nullptr，將鏈表的后k個節點和前 n - k個節點拼接到一塊，并讓head指向新的頭節點(p->next)，新的尾節點即p節點的next指標指向null，
4、最后回傳鏈表的新的頭節點head，
時間復雜度分析： 鏈表一共被遍歷兩次，因此總的時間復雜度為 O ( n ) O(n) O(n)， n n n是鏈表的長度，
3、c++代碼
/**
* Definition for singly-linked list.
* 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 || !k) return head;
int n = 0; //鏈表的長度
ListNode* tail; //尾節點
for(ListNode* p = head; p ; p = p->next){
tail = p;
n++;
}
k %= n;
ListNode* p = head;
for(int i = 0; i < n - k - 1; i++) p = p->next; //找到鏈表的第n-k個節點
tail->next = head;
head = p->next;
p->next = nullptr;
return head; //回傳新的頭節點
}
};
4、java代碼
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null|| k == 0) return head;
int n = 0; //鏈表的長度
ListNode tail = null; //尾節點
for(ListNode p = head; p != null ; p = p.next){
tail = p;
n++;
}
k %= n;
ListNode p = head;
for(int i = 0; i < n - k - 1; i++) p = p.next; //找到鏈表的第n-k個節點
tail.next = head;
head = p.next;
p.next = null;
return head; //回傳新的頭節點
}
}
原題鏈接： 61. 旋轉鏈表
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/301092.html
標籤：其他
上一篇：Django，啟航（一）相關準備