1. 原題鏈接：https://leetcode.com/problems/reverse-linked-list-ii/
2. 解題思路
- 采用頭插法進行反轉
- 利用啞節點將邊界case轉化為一般case
3. 演算法
- head2指標用于進行頭插操作的頭部指標
- 首先，將head2指標指向鏈表m-1的位置
- 然后，設定prev和cur指標遍歷m到n-1位置的鏈表，依次對這些節點進行反轉
4. 實作
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
ListNode dummy(-1);
dummy.next = head; //創建一個包含啞節點的鏈表
//遍歷到m-1的位置，當m為1時，此時啞節點就可以將這種邊界case轉化為一般case
ListNode *prev = &dummy;
for(int i = 0; i < m-1; i++){
prev = prev->next;
}
ListNode * const head2 = prev;
//采用頭插法反轉鏈表
//反轉至少需要兩個節點，通過prev和cur兩個節點實作反轉
prev = head2->next;
ListNode *cur = prev->next;
for(int i = m; i < n; i++){
prev->next = cur->next;
cur->next = head2->next;
head2->next = cur; //頭插法
cur = prev->next;
}
return dummy.next;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/88234.html
標籤：其他