删除链表的节点-剑指18（链表-虚拟头结点-c）

╰半橙微兮° 2022-11-18 10:50 123阅读 0赞

题目：

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。  
示例 1:

输入: head = \[4,5,1,9\], val = 5  
输出: \[4,1,9\]  
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.  
示例 2:

输入: head = \[4,5,1,9\], val = 1  
输出: \[4,5,9\]  
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明：

题目保证链表中节点的值互不相同  
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法：  
这道题并不难，考虑对下面的代码进行一些改进，基础的想法就是如果当前结点的值是我们寻找的值，就将当前结点的下一个结点的值赋给当前结点，然后令当前结点指向下一个结点的next域。但是如果当前结点为头节点这时候需要单独考虑，另外当前结点为尾结点此时需要使当前结点的前一个结点指向NULL，所以就需要一个指针记录前驱结点。

上面比较复杂，需要考虑多种情况，一个改进的方法，加一个虚拟头节点，这时候不用单独考虑要删除的结点是头结点和尾结点的情况了。尽管两种算法的时间复杂度O(n)，空间复杂度O(1)，这个没改善，但是从代码的理解与写法上还是有较大的变化的。

**基础版代码：**

struct ListNode* deleteNode(struct ListNode* head, int val){ 
        if(head == NULL)
        { 
            return head;
        }
        if(head->next == NULL && head->val == val)
        { 
             head = NULL;
             return head;
        }
        struct ListNode* curr = head;
        struct ListNode* pre = NULL;
        while(curr != NULL)
        { 
            if(curr->val == val)
            { 
                struct ListNode* pnext = curr->next;
                if(pnext != NULL)
                { 
                    curr->val = pnext->val;
                    curr->next = pnext->next;
                }
                else
                { 
                    curr = NULL;
                    pre->next = curr;
                    break;
                }
            }
            pre = curr;
            curr = curr->next;
        }
        return head;
    }

**改进版代码：**

struct ListNode* deleteNode(struct ListNode* head, int val){ 
        if(head == NULL)
        { 
            return head;
        }
    	//添加虚拟头节点
        struct ListNode* dummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
        dummyHead->next = head;
        struct ListNode* pre = dummyHead;
        struct ListNode* curr = head;
        while(curr != NULL)
        { 
            if(curr->val == val)
            { 
                pre->next = curr->next;
            }
            else
            { 
                 pre = curr;
            }
            curr = curr->next;
        }
        return dummyHead->next;
    }

小结：如果需要分情况单独考虑头结点和尾结点，就考虑添加虚拟头结点，一般情况下就可以避免复杂的分类讨论。

--------------------

再拿一道和这道类似，但比这道简单的.

**力扣237. 删除链表中的节点**  
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

示例 1：

输入：head = \[4,5,1,9\], node = 5  
输出：\[4,1,9\]  
解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.  
示例 2：

输入：head = \[4,5,1,9\], node = 1  
输出：\[4,5,9\]  
解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

提示：  
链表至少包含两个节点。  
链表中所有节点的值都是唯一的。  
给定的节点为非末尾节点并且一定是链表中的一个有效节点。  
不要从你的函数中返回任何结果。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/delete-node-in-a-linked-list  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

void deleteNode(struct ListNode* node) { 
        node->val = node->next->val;
        node->next = node->next->next;
        
    }

思路很简单，这道题考察的是对链表的理解，删除某个结点可以转换为将后一个结点的值赋给它，然后删除它的下一个结点。