文章目錄
- 題目描述
- 思路一
- 代碼實作
- 思路二
- 代碼實作
題目描述
給你一個鏈表的頭節點 head 和一個整數 val ，請你洗掉鏈表中所有滿足 Node.val == val 的節點，并回傳 新的頭節點 ，（題目來源）
思路一
要移除鏈表中值為val的結點，我們肯定是要將鏈表遍歷一遍，關鍵是我們在遍歷的程序中應該如何操作，我們考慮問題的時候，可以先考慮比較常見的情況，再考慮特殊情況，
一、考慮常見情況
要移除某一結點，也就是讓該結點的前一個結點指向待移除結點的后一個結點，然后將待移除結點釋放即可，我們可以定義3個指標變數：prev，cur，next ，
prev：記錄待排查結點的前一個結點位置（previous），
cur：記錄當前正在排查的結點位置（current），
next：記錄待排查結點的后一個結點（next），
當cur指標指向的結點并非待移除的結點時，3個結點依次向后移動，
當cur指標指向待移除的結點時，我們首先讓prev指標指向的結點指向next，然后將cur指標指向的結點釋放掉，并將next指標賦值給cur指標，next指標再后移，
如此進行下去，直到鏈表遍歷完畢，那么值為val的結點也就洗掉了，
二、考慮特殊情況
常見情況的分析往往只能解決問題的一般情況，并不能解決問題的極端情況，要真正解決問題，我們需要考慮到問題的極端情況，例如，當待移除的結點是第一個結點或是最后一個結點的情況，當鏈表為空的情況，
1.當鏈表的第一個結點為待移除的結點時
這時我們需要先將頭指標指向next，然后釋放cur指向的結點，并將next指標賦值給cur指標，next指標再后移，
2.當鏈表的最后一個結點為待移除的結點時
當排查到最后一個結點時，cur指向最后一個結點，next指標指向該結點指向的位置，即NULL，
我們用上面常規情況的方法對其進行分析，發現常規情況的思路適用于這種特殊情況，并且發現遍歷的終止條件，就是當cur為NULL的時候遍歷停止，
3.當傳入鏈表為空時
我們可以發現，若傳入的鏈表為空鏈表（NULL），cur指標的值一開始就為空，而我們遍歷的終止條件就是當cur為NULL時停止遍歷，所以當傳入鏈表為空時，直接執行到函式末尾，即回傳頭指標（NULL），
代碼實作
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* prev = NULL;//記錄待排查結點的前一個結點位置
struct ListNode* cur = head;//記錄當前正在排查的結點位置
while (cur != NULL)//當cur為空時，回圈停止
{
if (cur->val == val)//當前排查的結點是待移除的結點
{
struct ListNode* next = cur->next;//記錄待排查結點的后一個結點位置
if (cur == head)//待移除的結點是鏈表的第一個結點
{
head = next;//頭指標指向next
free(cur);//釋放第一個結點
cur = next;//將next指標賦值給cur指標
}
else//待移除的結點不是鏈表的第一個結點
{
prev->next = next;//prev指標指向的結點指向next
free(cur);//將cur指標指向的結點釋放掉
cur = next;//將next指標賦值給cur指標
}
}
else//當前排查的結點不是待移除的結點
{
prev = cur;//指標后移
cur = cur->next;//指標后移
}
}
return head;//回傳新的頭指標
}
思路二
我們可能覺得思路一的代碼比較復雜，當我們要移除某一個結點時，還需要判斷該結點是否為第一個結點，那么有沒有什么辦法可以不用進行這一步操作呢？
回答是肯定的，辦法就是在傳入的鏈表前面強行加上一個頭結點，并讓鏈表原來的頭指標指向該頭結點，這樣我們就不用判斷待移除的結點是否為第一個結點了（因為現在第一個結點是頭結點），
在加了頭結點后，我們就只需要根據常見情況的邏輯進行代碼的撰寫即可，但是有一點不能忘記，就是在遍歷完鏈表后要將頭結點指向的位置（即第一個結點的位置）賦值給頭指標，并將頭結點釋放掉，最后才能回傳頭指標，
代碼實作
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* guard = (struct ListNode*)malloc(sizeof(struct ListNode));//申請一個頭結點，回傳其地址
guard->next = head;//讓頭結點指向鏈表的第一個結點
struct ListNode* cur = guard->next;//cur指標指向原鏈表第一個結點
struct ListNode* prev = guard;//prev指標指向頭結點
while (cur != NULL)//當cur為空時，回圈停止
{
if (cur->val == val)//當前排查的結點是待移除的結點
{
struct ListNode* next = cur->next;//記錄待排查結點的后一個結點位置
prev->next = next;//prev指標指向的結點指向next
free(cur);//將cur指標指向的結點釋放掉
cur = next;//將next指標賦值給cur指標
}
else//當前排查的結點不是待移除的結點
{
prev = cur;//指標后移
cur = cur->next;//指標后移
}
}
head = guard->next;//將頭結點指向的位置賦值給頭指標，使頭指標指向鏈表第一個結點
free(guard);//釋放頭結點
guard = NULL;//及時置空
return head;//回傳新的頭指標
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/274755.html
標籤：其他
上一篇：理解閉包