• 题目难度：肥肠煎蛋

• 题目描述：

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

• 此题对比原题有改动

• 题目保证链表中节点的值互不相同

• 该题只会输出返回的链表和结果做对比，所以若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

• 数据范围:
  0<=链表节点值<=10000
  0<=链表长度<=10000

• 示例1:

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

两种写法：

• 写法一：直接用源head，需要单独考虑删除头节点

  时间复杂度：O(n)

  class Solution {
  public:
    ListNode* deleteNode(ListNode* head, int val) {
        if(head == nullptr) return head;
        ListNode* cur = head;
        // if delete head node
        if(head->val == val) head = head->next;
        // others node
        while(cur->next) {
            if(cur->next->val == val) {
                cur->next = cur->next->next;
                break;
            }
            cur = cur->next;
        }
        return head;
    }
  };

• 写法二：虚拟头节点

  时间复杂度：O(n)

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

  🤓🤓🤓🤓🤓🤓🤓🤓🤓🤓🤓🤓🤓🤓🤓🤓🤓🤓🤓🤓