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

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

注意：此题对比原题有改动

示例 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 被删除的节点

C++

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

    }
};

C

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* deleteNode(struct ListNode* head, int val){

}

题中说了链表中的节点值互不相同，也就是说最多只能删除一个。最简单的一种方式就是双指针求解，我们使用两个指针一个指向当前的节点，一个指向当前的上一个节点，以

示例1为例画个图看下

头节点和尾节点，为了保证头节点的不变性，我参考了给定一个节点如何删除的方法，就是狸猫换太子法，这样可以保证前一个节点的地址永远不变，所以这样的时候返回一个head就很不错。 还有一个小提示，p->next才等价于 p->next != NULL

/**
 \* Definition for singly-linked list.
 \* struct ListNode {
 \*   int val;
 \*   struct ListNode *next;
 \* };
 */
struct ListNode* deleteNode(struct ListNode* head, int val){
  struct ListNode * p = head , * prev = head;
  while(p -> next != NULL && p -> val != val){
     prev = p;
     p = p -> next;
  }
  if(p->next){
     struct ListNode * q = p->next;//知识要结合起来，在函数内定义一个变量存放在栈区，而malloc动态申请的存放在堆区
     p -> val = q -> val;
     p -> next = q -> next;
     free (q);
  } // 这部分操作这样写可以保证头节点的地址永远不变     
  else if(p -> val == val){
     prev -> next = NULL;
     free(p);
  }
  return head ;
}

思路：遍历链表，在节点head处考虑。

当head.val == val时，要删除head节点，那么，返回节点后面的链表头head->next。

当head.val ！= val时，要在head节点之后的部分继续删除。递归执行删除算法。

注意删除后，剩余的链表要再次拼接到head的后面。

class Solution {
public:
  ListNode* deleteNode(ListNode* head, int val) {
     if(!head) return head;
     if(head->val == val) return head->next;
     //递归删除
     head->next = deleteNode(head->next,val);
     return head;
  }
};

思路：遍历链表，开始在p=head处考虑。

当p->val == val时，删除p，返回p后面的链表头节点。

当p->next->val ！= val时，向后遍历，直到p->next->val == val时止。删除p->next即可。

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