删除无序链表的重复数字

思路

  1. 选择排序+删除连续重复值(结果被排序)
  2. 选择直接删除重复值
  3. hash删除重复值

代码

用了三种方法来实现


# include <bits/stdc++.h>
using namespace std;

struct list_node{
    int val;
    struct list_node * next;
};

list_node * input_list()
{
    int val, n;
    scanf("%d", &n);
    list_node * phead = new list_node();
    list_node * cur_pnode = phead;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &val);
        if (i == 1) {
            cur_pnode->val = val;
            cur_pnode->next = NULL;
        }
        else {
            list_node * new_pnode = new list_node();
            new_pnode->val = val;
            new_pnode->next = NULL;
            cur_pnode->next = new_pnode;
            cur_pnode = new_pnode;
        }
    }
    return phead;
}

list_node *sort_linker(list_node *head) {
    list_node whead = {0, head};
    list_node *p = &whead, *q = nullptr;
    while(p && p->next) { // w w w 
        q = p;
        list_node *minq = q;
        while(q->next) { // 
            if(q->next && q->next->val < minq->next->val) {
                minq = q;
            }
            q = q->next;
        }
        list_node *t = minq->next;
        minq->next = t->next;
        t->next = p->next;
        p->next = t;
        p = p->next;
        
    }
    return whead.next;
    
}

list_node *remove_rep_sorted(list_node * head)
{
    head = sort_linker(head);
    // cout << "a "<< endl;
    list_node *p = head, *nxt = head->next;
    while(nxt) {
        
        if(nxt->val == p->val) {
            p->next = nxt->next;
            delete (nxt);
            
        }
        p = p->next;
        if(p) nxt = p->next;
        else nxt = nullptr;
    }
    return head;
    
}


list_node *remove_rep_n2(list_node *head)
{

    list_node *p = head, *ep = head;
    while(p && p->next) {
        ep = p;
        while(ep && ep->next) {
            if(p->val == ep->next->val) {
                list_node *t = ep->next;
                ep->next = t->next;
                delete (t);
            }
            ep = ep->next;
        }
        p = p->next;
    }
    return head;
    
}


list_node *remove_rep(list_node *head) //hash
{
    
    list_node *p = head, *pre =nullptr;
    set<int> hash;
    
    while(p) {
        if(hash.count(p->val) == 0) {
            hash.insert(p->val);
        }else{
            pre->next = p->next;
            delete(p);
            p = pre;
        }
        if(p == pre) p = p->next;
        else {
            pre = p;
            p = p->next;
        }
    }
    return head;
    
}


void print_list(list_node * head)
{
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

int main ()
{
    list_node * head = input_list();
    list_node * new_head = remove_rep(head);
    print_list(new_head);
    return 0;
}

Comments