18.删除链表的结点 (Easy)*

题目描述*

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

返回删除后的链表的头结点。

示例*

输入: head = [4,5,1,9], val = 5

输出: [4,1,9]

输入: head = [4,5,1,9], val = 1

输出: [4,5,9]

代码*

这个题是给出要删除的值，所以只能遍历。

原书的题目是给定了要删除的结点，那我们就可以用 O(1) 时间删除，以后继结点替代当前结点，要删除尾结点时才需要从头遍历。

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode *newHead = new ListNode(-1);
        newHead->next = head;
        ListNode *p = newHead;
        while(p->next != nullptr) {
            if(p->next->val == val) {
                p->next = p->next->next;
                break;
            }
            p = p->next;
        }
        return newHead->next;
    }
};

最后更新: July 23, 2022