18剑指OFFER之删除链表中重复的节点

参考资料：

[1]好的参考资料1：https://blog.csdn.net/qq_24486393/article/details/51868590
[2]好的参考资料2：https://www.cnblogs.com/linkstar/p/5995066.html

关键词：

两个指针、如何删除重复的节点、如何防止链表的第一个节点被删除

类似题目：

leetcode
删除链表的节点
 remove-duplicates-from-sorted-list-ii
remove-duplicates-from-sorted-list

思路：

remove-duplicates-from-sorted-list-ii
如果当前节点和当前节点的下一个节点的值相同的话，那么找到和当前节点的值不相同的第一个节点，将前一个节点指向当前节点。
如果当前节点和当前节点的下一个节点的值不同的话，那么前一个节点为当前节点，当前节点为当前节点的下一个节点。

全部删除和只留一个就是一行代码的区别！！！！

自己的解答：

删除链表的节点

参考资料：剑指OFFER课本面试题18：
考虑各种情况：

void DeleteListNode(ListNode* pHead, ListNode* pDeleteNode)
{
    //1.如果链表就一个节点的话，或者没有节点
    if (pHead == nullptr || pHead->m_pNext == nullptr)
    {
        pHead = nullptr;
        return;
    }

    ListNode* pNode = pHead;
    //如果删除的节点为链表的尾节点,那么只能从头到尾进行遍历
    if (pDeleteNode->m_pNext == nullptr)


    {
        while (pNode->m_pNext != pDeleteNode)
        {
            pNode = pNode->m_pNext;
        }
        pNode->m_pNext = nullptr;
        return;
    }

    //如果删除的节点位于前面的节点
    pDeleteNode->m_nKey = pDeleteNode->m_pNext->m_nKey;
    pDeleteNode->m_pNext = pDeleteNode->m_pNext->m_pNext;

}

Leetecode上的解答（这里只考虑一种情况）：

/**
 * 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) {
     
        node->val = node->next->val;
        node->next = node->next->next;
        return;
        
        
        
    }
};

remove-duplicates-from-sorted-list-ii

改进版：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        
        //如果节点为空或者只有一个节点的话，那么返回
        if (head == nullptr || head->next == nullptr)
            return head;

        //定义一个节点，防止投节点被删除
        ListNode* pFirst = new ListNode(0);
        pFirst->next = head;

        //定义前一个节点和当前节点
        ListNode* pPrev = pFirst;
        ListNode* pNode = head;


        while (pNode != nullptr && pNode->next != nullptr)
        {
            //1.如果当前节点的值和当前节点的下一个节点相同的话，那么找一个不相同的节点,其他是否为空的都是为了程序的正常运行
            if (pNode->val == pNode->next->val)
            {
                while(pNode!= nullptr&& pNode->next!= nullptr && pNode->val == pNode->next->val)//特别注意这个的执行顺序啊
                    pNode = pNode->next;
                pPrev->next = pNode->next;
                pNode = pNode->next;//要注意当前节点
            }
            else
            {
                pPrev = pNode;
                pNode = pNode->next;
                
            }
            
        }
        return pFirst->next;
    
    }
};

remove-duplicates-from-sorted-list-i