题目描述

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

• 1.此题对比原题有改动
• 2.题目保证链表中节点的值互不相同
• 3.该题只会输出返回的链表和结果做对比，所以若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

数据范围:

0<=链表节点值<=10000
0<=链表长度<=10000

示例1

输入：{2,5,1,9},5
返回值：{2,1,9}
说明：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 2 -> 1 -> 9 

示例2

输入：{2,5,1,9},1
返回值：{2,5,9}
说明：
给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 2 -> 5 -> 9   

思路 & 解答

如果我们要删除链表里面的一个节点，其实就是将前置节点的next 直接指向当前节点的后置节点，这样在链表中再也找不到该节点了，也就是相当于删除了。

假设有一个链表，我们需要删除里面的 5:

首先需要判断链表头结点是不是为空，如果为空，那么就直接返回NULL，如果等于我们要找的，那么直接返回下一个节点引用即可。

如果不符合以上说的，那么我们需要新建一个前置节点pre,与现在的链表连接在一起：

然后初始化一个 cur 节点表示当前节点，指向 head 节点：

cur 不为空，cur 和 pre 后移：

发现 cur 正是我们需要查找的 5 ，那么记录下 5 的下一个节点 1 ,也就是next:

cur 的 next 指向 NULL,使用 pre 的 next 指向刚刚记录的 next:

简化链表也就是：

取之前虚拟的头结点的后一个节点，就是删除掉之后的新链表：

Java 代码实现如下：

class ListNode {
    int val;
    ListNode next = null;

    public ListNode(int val) {
        this.val = val;
    }
}

public class Solution13 {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        if (head.val == val) {
            return head.next;
        }
        // 用一个节点将头结点链接起来
        ListNode pre = new ListNode(-1);
        pre.next = head;

        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            cur = cur.next;
            pre = pre.next;
            // 如果相等，则指针指向下一个节点
            if (cur.val == val) {
                next = cur.next;
                break;
            }
        }
        cur.next = null;
        // 将前置节点直接连接后一个节点，相当于删除掉了该节点
        pre.next = next;
        return head;
    }
}

C++ 代码实现如下：

struct ListNode {
    int val;
    struct ListNode *next;

    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *deleteNode(ListNode *head, int val) {
        if (head == NULL) {
            return NULL;
        }
        if (head->val == val) {
            return head->next;
        }
        // 用一个节点将头结点链接起来
        ListNode *pre = new ListNode(-1);
        pre->next = head;

        ListNode *cur = head;
        ListNode *next = NULL;
        while (cur != NULL) {
            cur = cur->next;
            pre = pre->next;
            // 如果相等，则指针指向下一个节点
            if (cur->val == val) {
                next = cur->next;
                break;
            }
        }
        cur->next = NULL;
        // 将前置节点直接连接后一个节点，相当于删除掉了该节点
        pre->next = next;
        return head;
    }
};