删除链表中重复的结点

题目

在一个排序的链表中，如何删除重复的结点？

思路

　设置一个preNode，用于记录当前结点的前一个结点，再设置一个布尔变量needDelete，如果当前结点和后一结点的值相同（记该值为dupVal），needDelete赋值为真。

　　当needDelete为真时，通过循环往后找到第一个不为dupVal的结点，把该结点设置为当前结点，并赋值给preNode.next，即相当于完成了删除操作；而当needDelete为假时，把当前结点和preNode往后移一位即可。

#include <iostream>
using namespace std;

struct node
{
    int data;
    struct node *next;
};
class Solution
{
    public:
        Solution();
        void create();
        void print();
        void delete_node(struct node *n);//删除链表中的结点 
        void delete_repate();//删除链表中重复的结点 
        node *head;
};
Solution::Solution()
{
    head=new node();
    head->next=nullptr;
    head->data=0;
}
void Solution::create()
{
    if(head==nullptr)
        return;
    auto t=head;
    int x;
    while(1)
    {
        cin>>x;
        if(x)
        {
            t->next=new node();
            t=t->next;
            t->data=x;
            t->next=nullptr;
        }
        else
        {
            t->next=nullptr;
            break;
        }
    }
} 
void Solution::print()
{
    auto n=head;
    while(n)
    {
        cout<<n->data<<endl;
        n=n->next;
    }
}
//把要删除的结点的下一结点的值复制到要删除的结点，然后把要删除的结点的下一结点删除 
void Solution::delete_node(struct node *n)//删除链表中的结点 
{
    if(head==nullptr||n==nullptr)
        return;
    if(n->next!=nullptr)//要删除的结点不是尾结点
    {
        auto pnext=n->next;
        n->data=pnext->data;
        n->next=pnext->next;
        
        delete pnext;
        pnext=nullptr;
    }
    else if(n==head)//要删除结点是头结点
    {
        auto t=head;
        head=head->next;
        delete t;
        t=nullptr;
    }
    else//删除的是尾结点 
    {
        auto pnext=head;
        while(pnext->next!=n)
            pnext=pnext->next;
        
        pnext->next=nullptr;
        delete n;
        n=nullptr;
    }
}int main()
{
    Solution s;
    s.create();
    s.delete_node(s.head);
    s.delete_repate();
    s.print();
    
    return 0;
}

 code2

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* head)
    {
        if(!head)
            return nullptr;
        
        ListNode *H=new ListNode(-1);
        H->next=head;
        ListNode *pre=H;
        ListNode *cur=H->next;
        while(cur)
        {
            auto next=cur->next;
            bool needDel=false;
            if(next&&cur->val==next->val)
                needDel=true;
            
            if(!needDel)
            {
                pre=cur;
                cur=cur->next;
            }
            else
            {
                auto del=cur;
                int val=cur->val;
                while(del&&del->val==val)
                {
                    next=del->next;
                    delete del;
                    del=nullptr;
                    del=next;
                }
                if(pre->val==H->val)
                    H->next=next;
                else
                    pre->next=next;
                cur=next;
            }
        }
        return H->next;
    }
};