203.移除鏈表元素
解題思路：
- 為鏈表新增一個虛擬頭節(jié)點路翻，定義一個當(dāng)前指針指向虛擬頭節(jié)點澳厢。通過while循環(huán)遍歷鏈表驼抹，只有當(dāng)前指針指向最后一個節(jié)點的時候毙驯，循環(huán)停止柱锹。
- 每次循環(huán)中哪自，首先判斷當(dāng)前指針指向的節(jié)點的下一個節(jié)點的元素是否為目標(biāo)值，如果為真禁熏，定義一個臨時變量指向即將刪除的下一個節(jié)點提陶，然后將即將刪除的節(jié)點中next信息傳遞給當(dāng)前節(jié)點的next，delete改臨時指針匹层，釋放下一個節(jié)點的空間隙笆。
- 如果為否，當(dāng)前指針指向下一個節(jié)點升筏。當(dāng)前指針指向節(jié)點的next為空之后撑柔，說明當(dāng)前指針已經(jīng)指向了最后一個指針，循環(huán)結(jié)束您访。
- 最后將虛擬頭節(jié)點中的next賦值給head頭指針铅忿，最后釋放虛擬頭節(jié)點的空間。
ListNode* dummyHead = new ListNode(0);
dummyHead->next = head;
ListNode* cur = dummyHead;
while (cur->next != NULL) {
if(cur->next->val == val) {
ListNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
} else {
cur = cur->next;
}
}
head = dummyHead->next;
delete dummyHead;
return head;
707.設(shè)計鏈表
解題思路;
- 設(shè)計一個鏈表類灵汪，一個完整的鏈表必須要包含頭指針檀训，所以為增添一個私有數(shù)據(jù)成員為指向鏈表頭結(jié)點的指針，指針類型為一個節(jié)點類型享言，所以要在類中明確節(jié)點的結(jié)構(gòu)峻凫，定義了一個結(jié)構(gòu)體，結(jié)構(gòu)體中的構(gòu)造函數(shù)用于初始化結(jié)構(gòu)體览露，不加構(gòu)造函數(shù)就沒辦法在括號中為節(jié)點初始化荧琼，只能借助于->和.來對節(jié)點中的元素進行初始化。私有成員還包含了size變量，用于判斷索引值是否合法命锄。
- 鏈表類的構(gòu)造函數(shù)中堰乔，開辟一個節(jié)點空間，同時初始化頭指針脐恩，但該節(jié)點為虛擬頭節(jié)點镐侯。另一方面size初始化為0；
- get函數(shù)實現(xiàn)過程驶冒，首先要判斷索引是否合法苟翻。定義臨時指針指向真實頭節(jié)點，這一點很關(guān)鍵只怎。后接while循環(huán)開始移動當(dāng)前指針，指針先移動怜俐，索引在移動身堡，索引會移動index位，指針也移動index位拍鲤，最終當(dāng)前指針指向目標(biāo)節(jié)點贴谎，直接取值。
class MyLinkedList {
public:
// 定義鏈表節(jié)點結(jié)構(gòu)體
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode(int val):val(val), next(nullptr){}
};
// 初始化鏈表
MyLinkedList() {
_dummyHead = new LinkedNode(0); // 這里定義的頭結(jié)點 是一個虛擬頭結(jié)點季稳，而不是真正的鏈表頭結(jié)點
_size = 0;
}
// 獲取到第index個節(jié)點數(shù)值擅这，如果index是非法數(shù)值直接返回-1， 注意index是從0開始的景鼠，第0個節(jié)點就是頭結(jié)點
int get(int index) {
if (index > (_size - 1) || index < 0) {
return -1;
}
LinkedNode* cur = _dummyHead->next;
while(index--){ // 如果--index 就會陷入死循環(huán)
cur = cur->next;
}
return cur->val;
}
// 在鏈表最前面插入一個節(jié)點仲翎，插入完成后，新插入的節(jié)點為鏈表的新的頭結(jié)點
void addAtHead(int val) {
LinkedNode* newNode = new LinkedNode(val);
newNode->next = _dummyHead->next;
_dummyHead->next = newNode;
_size++;
}
// 在鏈表最后面添加一個節(jié)點
void addAtTail(int val) {
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while(cur->next != nullptr){
cur = cur->next;
}
cur->next = newNode;
_size++;
}
// 在第index個節(jié)點之前插入一個新節(jié)點铛漓，例如index為0溯香，那么新插入的節(jié)點為鏈表的新頭節(jié)點。
// 如果index 等于鏈表的長度浓恶，則說明是新插入的節(jié)點為鏈表的尾結(jié)點
// 如果index大于鏈表的長度玫坛，則返回空
void addAtIndex(int index, int val) {
if (index > _size) {
return;
}
LinkedNode* newNode = new LinkedNode(val);
LinkedNode* cur = _dummyHead;
while(index--) {
cur = cur->next;
}
newNode->next = cur->next;
cur->next = newNode;
_size++;
}
// 刪除第index個節(jié)點，如果index 大于等于鏈表的長度包晰，直接return湿镀，注意index是從0開始的
void deleteAtIndex(int index) {
if (index >= _size || index < 0) {
return;
}
LinkedNode* cur = _dummyHead;
while(index--) {
cur = cur ->next;
}
LinkedNode* tmp = cur->next;
cur->next = cur->next->next;
delete tmp;
_size--;
}
// 打印鏈表
void printLinkedList() {
LinkedNode* cur = _dummyHead;
while (cur->next != nullptr) {
cout << cur->next->val << " ";
cur = cur->next;
}
cout << endl;
}
private:
int _size;
LinkedNode* _dummyHead;
};
206.反轉(zhuǎn)鏈表
解題思路：
雙指針法：定義三個指針，一個當(dāng)前指針伐憾，由于沒有虛擬節(jié)點勉痴，它直接指向頭節(jié)點。一個臨時指針用于保存之后節(jié)點的信息树肃。一個pre指針用于指向前一個節(jié)點蚀腿。
首先保存下一個節(jié)點的位置，將當(dāng)前節(jié)點指向前一個節(jié)點，pre節(jié)點指向當(dāng)前節(jié)點莉钙，當(dāng)前指針指向下一個節(jié)點廓脆。
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* temp; // 保存cur的下一個節(jié)點
ListNode* cur = head;
ListNode* pre = NULL;
while(cur) {
temp = cur->next; // 保存一下 cur的下一個節(jié)點，因為接下來要改變cur->next
cur->next = pre; // 翻轉(zhuǎn)操作
// 更新pre 和 cur指針
pre = cur;
cur = temp;
}
return pre;
}
};
遞歸法
class Solution {
public:
ListNode* reverse(ListNode* pre,ListNode* cur){
if(cur == NULL) return pre;
ListNode* temp = cur->next;
cur->next = pre;
// 可以和雙指針法的代碼進行對比磁玉，如下遞歸的寫法停忿，其實就是做了這兩步
// pre = cur;
// cur = temp;
return reverse(cur,temp);
}
ListNode* reverseList(ListNode* head) {
// 和雙指針法初始化是一樣的邏輯
// ListNode* cur = head;
// ListNode* pre = NULL;
return reverse(NULL, head);
}
};
