18劍指OFFER之刪除鏈表中重復(fù)的節(jié)點

參考資料：

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

關(guān)鍵詞：

兩個指針包个、如何刪除重復(fù)的節(jié)點俊戳、如何防止鏈表的第一個節(jié)點被刪除

類似題目：

leetcode
刪除鏈表的節(jié)點
 remove-duplicates-from-sorted-list-ii
remove-duplicates-from-sorted-list

思路：

remove-duplicates-from-sorted-list-ii
如果當(dāng)前節(jié)點和當(dāng)前節(jié)點的下一個節(jié)點的值相同的話威蕉，那么找到和當(dāng)前節(jié)點的值不相同的第一個節(jié)點沛慢，將前一個節(jié)點指向當(dāng)前節(jié)點。
如果當(dāng)前節(jié)點和當(dāng)前節(jié)點的下一個節(jié)點的值不同的話料扰，那么前一個節(jié)點為當(dāng)前節(jié)點，當(dāng)前節(jié)點為當(dāng)前節(jié)點的下一個節(jié)點。

全部刪除和只留一個就是一行代碼的區(qū)別Ｅ祷觥！＜缆筷笨！

自己的解答：

刪除鏈表的節(jié)點

參考資料：劍指OFFER課本面試題18：
考慮各種情況：

void DeleteListNode(ListNode* pHead, ListNode* pDeleteNode)
{
    //1.如果鏈表就一個節(jié)點的話，或者沒有節(jié)點
    if (pHead == nullptr || pHead->m_pNext == nullptr)
    {
        pHead = nullptr;
        return;
    }

    ListNode* pNode = pHead;
    //如果刪除的節(jié)點為鏈表的尾節(jié)點,那么只能從頭到尾進行遍歷
    if (pDeleteNode->m_pNext == nullptr)


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

    //如果刪除的節(jié)點位于前面的節(jié)點
    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) {
        
        //如果節(jié)點為空或者只有一個節(jié)點的話龟劲，那么返回
        if (head == nullptr || head->next == nullptr)
            return head;

        //定義一個節(jié)點胃夏，防止投節(jié)點被刪除
        ListNode* pFirst = new ListNode(0);
        pFirst->next = head;

        //定義前一個節(jié)點和當(dāng)前節(jié)點
        ListNode* pPrev = pFirst;
        ListNode* pNode = head;


        while (pNode != nullptr && pNode->next != nullptr)
        {
            //1.如果當(dāng)前節(jié)點的值和當(dāng)前節(jié)點的下一個節(jié)點相同的話，那么找一個不相同的節(jié)點,其他是否為空的都是為了程序的正常運行
            if (pNode->val == pNode->next->val)
            {
                while(pNode!= nullptr&& pNode->next!= nullptr && pNode->val == pNode->next->val)//特別注意這個的執(zhí)行順序啊
                    pNode = pNode->next;
                pPrev->next = pNode->next;
                pNode = pNode->next;//要注意當(dāng)前節(jié)點
            }
            else
            {
                pPrev = pNode;
                pNode = pNode->next;
                
            }
            
        }
        return pFirst->next;
    
    }
};

remove-duplicates-from-sorted-list-i