删除元素最常见的做法是

1.利用curNode指针遍历一遍链表，保存前一指针preNode

2.当curNode找到要删除元素，$preNode-next = $curNode->next

如LeetCode：203.移除链表元素 和 83.删除排序链表中的重复元素 解法均如上，本文不做解析

---

目录

237.删除链表中的节点

82. 删除排序链表中的重复元素 II

19. 删除链表的倒数第N个节点

---

237.删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

 

示例 1:

输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2:

输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.

说明:

• 链表至少包含两个节点。
• 链表中所有节点的值都是唯一的。
• 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
• 不要从你的函数中返回任何结果。

解析：难点在于直接给出一个待删除节点的指针，因此无法获取待删除节点的前一个节点指针

解法：一般解决链表问题，是不可以修改节点的值，但是这道题就需要用这种思想

1.得到当前节点node

2.获得node的下一节点delNode，并赋值给node，node->val = delNode->val

3.将node指针指向delNode的下一节点，再将delNode释放掉即可

LeetCode对于该题没有PHP的解题语言选择，因此本题采用C++解决

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        if(node == NULL)
            return;
        if(node->next == NULL){
            delete node;
            node = NULL;
            return;
        }
        node->val = node->next->val;       //赋值，将下一节点的值赋给当前节点
        ListNode* delNode = node->next;    //得到delNode
        node->next = delNode->next;        //将当前节点的指向delNode的下一节点

        delete delNode; //释放delNode的空间
        return ;
    }
};

---

82. 删除排序链表中的重复元素 II

给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现 的数字。

示例 1:

输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:

输入: 1->1->1->2->3
输出: 2->3

解析：与83题区别在于，该题需要将重复的元素全部删除

解法：

1.构建虚拟头节点、遍历一遍链表    

2.当无重复时，正常遍历  

3.当找到重复元素时，二层遍历，直到找到不重复的元素，$curNode->next指向该元素

class Solution {
    function deleteDuplicates($head) {
        //建立一个虚拟头节点
        $dummyHead = new ListNode(null);
        $dummyHead->next = $head;
        $curNode = $dummyHead;
        while ($curNode->next) {
            $val = $curNode->next->val;
            $end = $curNode->next;
            //判断是否有重复元素
            if($end->next && $end->next->val == $val){
                //有则二层遍历，直到找到不是该值的节点
                while ($end->next && $end->next->val == $val) {
                    $end = $end->next;
                }
                $curNode->next = $end->next;
            }else{
                $curNode = $curNode->next;
            }
        }
        return $dummyHead->next;
    }
}

---

19. 删除链表的倒数第N个节点

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：给定的 n 保证是有效的。

解析：该题可以先遍历一遍链表，获取链表长度，再进行第二次遍历，将节点删除，但是需要遍历两遍链表，对于时间复杂度来说有更好的解法

解法：

1.利用双指针的思想$curNode当前节点和$preNode前节点

2.双指针的差距保持在$n的距离

3.只遍历一遍链表，直到$curNode为空，跨越delNode节点，即删除节点

class Solution {
    function removeNthFromEnd($head, $n) {
        //双指针
        $dummyHead = new ListNode(null);
        $dummyHead->next = $head;
        $curNode = $preNode = $dummyHead;
        $count = 0;
        while($curNode->next){
            $curNode = $curNode->next;
            //移动双指针，直到指针距离 为 $n
            if($count<$n){
                $count++;
            }else{
                $preNode = $preNode->next;
            }
        }
        $delNode = $preNode->next;          //遍历完后，$preNode指向待删除元素的前一元素
        $preNode->next = $delNode->next;    //跨越该元素即可删除待删除元素
        return $dummyHead->next;
    }
}