删除单向链表中的重复结点

雨点打透心脏的1/2处 2023-03-14 05:59 23阅读 0赞

完成函数dubdel的编写，该函数删除单向链表中的重复结点，如果链表中存在重复结点（除next指针外的其它数据成员的值相同）时，保留离链首最近的结点。

样例输入：

5
    1 2 3 2 4

样例输出：

1 2 3 4

#include<iostream>
    #include <string>
    using namespace std;
    struct Node 
    { 
        int num;
        Node *next;
    };
    Node * dubdel(Node *head)
    { 
     int a[1000],n=0,i;
     Node *cur=head,*pre=NULL;
     while(cur)
     { 
      bool del=false;
      for(i=0;i<n;i++)
      { 
       if(a[i]==cur->num)
       { 
        del=true;
        break;
       }
      }
      if(del)
      { 
       pre->next=cur->next;
       delete cur;
       cur=pre->next;
      }
      else
      { 
       a[n++]=cur->num;
       pre=cur;
       cur=cur->next;
      }
      } 
      return head;
    }
    void deleteList(Node *head)
    { 
        Node *tmp;
        while (head)
        { 
            tmp = head->next;
            delete head;
            head = tmp;
        }
    }
    void printList(Node *head)
    { 
        while(head)
        { 
            cout<<head->num<<" ";
            head = head->next;
        }
        cout<<endl;
    }
    Node * createList(int a[], int len)
    { 
        Node *head = NULL;
        if(len<1)
            return head;
        for(int i = len - 1; i >= 0; i--)
        { 
            Node *tmp = new Node;
            tmp->num = a[i];
            tmp->next = head;
            head = tmp;
        }
        return head;
    }
    int main()
    { 
        int len;
        cin>>len;
        int s[len];
        for(int j = 0; j < len; j++)
        { 
            cin>>s[j];
        }
        Node * head = createList(s,len);
        head = dubdel(head);
        printList(head);
        deleteList(head);
        return 0;
    }