【链表】删除链表的节点（ leetcode18）

痛定思痛。 2022-10-12 12:14 235阅读 0赞

## 一、题目 ##

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。
    返回删除后的链表的头节点。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20210704182834839.png]

## 二、题解 ##

本题是一道简单的套路题，首先回忆一下删除链表节点的操作：首先定义两个指针pre、curr；然后从首到尾遍历一次链表，如果要删除当前节点，只需要：pre->next = curr->next。

**关键在于：head->val也有可能等于val，所以本题返回的不是head，而是第一个不等于val值的节点**。具体做法也很简单，只需在遍历之前，加上：

while(head)
    {         
         if(head->val == val)
             head = head->next;
         else
             break;
     }

## 三、实现 ##

根据以上的分析，相应的C++实现如下：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    public:
        ListNode* deleteNode(ListNode* head, int val) { 
            while(head)
            {         
                if(head->val == val)
                    head = head->next;
                else
                    break;
            }
            //此时的head是第一个不等于val的节点
            ListNode* curr = head;
            ListNode* pre = curr;
            while(curr->next)
            { 
                curr = curr -> next;
                if(curr->val==val) // 如果等于，则删除当前节点；但不更新pre，因为curr->next 也有可能是val
                    pre->next = curr->next;
                else
                    pre = curr; // 不相同，则更新pre
            }
            return head;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dqaW5qaWU_size_16_color_FFFFFF_t_70]: /images/20221005/73de10596e7140a1b390ec049343610c.png
[20210704182834839.png]: /images/20221005/e4d96d9e24874dff8f2d6de25cda2c6d.png