1. 原題鏈接：https://leetcode.com/problems/reverse-linked-list/
2. 解題思路
- 注意：一般情況下，反轉操作需要有兩個指標
- 遞回思路
- 遞回類似于堆疊操作的入堆疊和出堆疊，關鍵在于入堆疊哪些資料？
- 針對這道題目，由于是反轉操作，所以需要入堆疊兩個指標，假定為prev和cur兩個指標
- 為了能夠反轉，prev指標應該為cur的next指標，只有這樣依次出堆疊的時候，prev指標才是指向反轉鏈表程序中的prev節點
- 迭代思路
- 采用兩個指標的頭插法反轉鏈表
3. 演算法
3.1 遞回演算法
- 首先，需要確定遞回函式的功能，此處的遞回函式功能是回傳原鏈表進行反轉之后的頭節點
- 遞回結束條件：原鏈表為慷訓者原鏈表只有一個節點
3.2 迭代演算法
- 創建一個啞節點用于向新鏈表的頭部插入節點
- 用prev和cur兩個指標進行反轉操作
4. 實作
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
遞回演算法
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == NULL || head->next == NULL) return head;
ListNode *new_prev = head->next; //存盤新構成的鏈表的最后一個節點
ListNode *new_head = reverseList(head->next); //反轉從下一個節點開始的鏈表
new_prev->next = head;
head->next = NULL;
return new_head;
}
};
迭代演算法
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head == NULL) return head;
ListNode dummy(-1);
dummy.next = head;
ListNode *head2 = &dummy;
ListNode *prev = head2->next;
ListNode *cur = prev->next;
while(cur != NULL){
prev->next = cur->next;
cur->next = head2->next;
head2->next = cur; //頭插法
cur = prev->next;
}
return dummy.next;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/88233.html
標籤：其他