题目描述

• 在一个排序的链表中，如何删除重复的节点？请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
• 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

题目解读

• 剑指Offer 122

代码

#include<iostream>
using namespace std;

struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    // 删除链表中重复数字
    ListNode* deleteDuplication(ListNode* pHead){
        ListNode *pre = NULL;
        ListNode *current = pHead;

        if(pHead == NULL){
            return NULL;
        }
        
        while(current){
            int value = current->val;
            ListNode *temp = current -> next;
            bool todelete = false;

            if(temp != NULL && value == temp -> val){
                todelete = true;
            }  

            if(!todelete){  // 当前节点和后一个节点不相同，即不重复
                pre = current;
                current = current->next;
            }
            else{   // 当前节点和后一个节点重复
                ListNode *todelNode = current;
                // 注意点，此处将判断非空放在前面，避免从空地址中取值
                while(todelNode != NULL && value == todelNode->val){
                    temp = todelNode -> next;
                    delete todelNode;  // 此句写不写在牛客网测试占用内存一样..
                    todelNode = temp;
                }

                if(pre == NULL){
                    pHead = temp;
                }
                else{
                    pre -> next = temp;
                }
                current = temp;
            }
        }
        return pHead;
    }

    // 输出链表
    void PrintList(ListNode *head){
        if(!head){
            cout<<"链表为空"<<endl;
        }
        else{
            while(head){
                cout<<head->val<<" ";
                head = head->next;
            }
            cout<<endl;
        }
    }

    // 创建链表
    ListNode* createList(){
        int node[10] = {1, 2, 2};
        int length = 3;
        
        ListNode *head = NULL;
        ListNode *tail = NULL;

        for(int i=0; i < length; i++){
            ListNode *p = new ListNode(node[i]);

            if(!head){
                head = p;
                tail = head;
            }
            else{
                tail -> next = p;
                tail = p;
            }
        }
        return head;
    }
};

int main(){
    Solution ss;
    ListNode *head = NULL;
    
    head = ss.createList();　　// 创建链表
    ss.PrintList(head);　　　　// 输出链表
    head = ss.deleteDuplication(head);  // 删除链表中重复数字
    ss.PrintList(head);      // 输出链表
    return 0;
}

总结展望

• 代码中 while(todelNode != NULL && value == todelNode->val){}，这句话至少折磨了两个小时，导致内存读写出错，后来找到原因前后位置写反，比如一个指针为空，但是你不知道，还要从里面读取数据，就会内存读出错，程序异常终止；所以应该把判断指针为空放到指针读数据前面
• 很不错的练习链表的题目