[Lc]面试题18删除链表的节点

题目

链表定义：

//Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

题解

这题简单，两个指针，一个指向cur，一个是cur之前pre。当cur的值为val时，pre的next指向cur的next

• 时间复杂度$O(n)$
• 空间复杂度$O(n)$

class Solution {
public:
    ListNode* deleteNode(ListNode* head, int val) {
        ListNode* dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *pre = dummy, *cur = head;
        while(cur){
            if(cur->val == val){
                pre->next = cur->next;
                break;
            }
            cur = cur->next;
            pre = pre->next;
        }
        return dummy->next;
    }
};

书上要求时间复杂度为O(1)，其题目是给了需要删除的节点（注意不是该节点的值）。这样就没法找到其前一个节点了，需要其他方法。

• 若该节点的next为nullptr，直接删除该节点
• 若不是，把后一个节点的值赋值给当前节点，然后该节点指向下一个节点的下一个节点即可