資料結構OJ題——移除鏈表元素
- 方法一：在原鏈表的基礎上遍歷
- 方法二：重新創建一個空鏈表，進行尾插
- 總結對比
方法一：在原鏈表的基礎上遍歷
struct ListNode* removeElements(struct ListNode* head, int val)
{
while (head != NULL && head->val == val) {
head = head->next;
}
if (head == NULL) {
return NULL;
}
struct ListNode* pre = head;
while (pre->next != NULL) {
/* 找到值為 val 的節點并洗掉 */
if (pre->next->val == val)
{
pre->next = pre->next->next;
}
else
{
/*沒找到繼續遍歷尋找 */
pre = pre->next;
}
}
return head;
}
下面兩幅圖是我在平板上寫的對極端情況的思考（這個地方很容易出錯），以及對
while (pre->next != NULL) {
/* 找到值為 val 的節點并洗掉 */
if (pre->next->val == val)
{
pre->next = pre->next->next;
}
這段代碼的理解（這段代碼非常的秒，有很多的妙用）.
方法二：重新創建一個空鏈表，進行尾插
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* newnode=NULL;
while(head!=NULL&&head->val==val)
{
head=head->next;
}
if(head==NULL)
{
return NULL;
}
struct ListNode*cur=head;
newnode=cur;
struct ListNode* tail=cur;
while(cur->next)
{
if(cur->next->val==val)
{
cur->next=cur->next->next; //cur=cur->next->next;//前面一種寫法就可以巧妙的避免連續2個6的情況，而后面的寫法不能
}
else
{
cur=cur->next;
tail->next=cur;
tail=tail->next;
}
}
tail->next=NULL;
return head;
}
這段代碼要注意的就是最后結束了，一定不要忘了把tail->next賦值為空
總結對比
方法一的思路比較容易想到，一個個遍歷過去，是的就保留，不是的就銷毀（也可以不銷毀，如代碼中一樣，直接跳到下下個節點去），不過這段代碼寫的時候很講究寫法和技巧，寫法不好的話，考慮的情況就很多，而且很復雜，再加上這段代碼的細節也很多，很容易出錯；方法二，代碼沒有太多的細節，寫起來簡單，但思路不容易想到，總的來說，在寫這種考你邏輯能力的oj題時，一定要多畫圖，畫圖時要想好每一步以及下一步應該怎么走，這中間也要把一些極端情況考慮進去.
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/291639.html
標籤：其他