CareerCup之2.1无序链表删除重复元素

【题目】

原文：

2.1 Write code to remove duplicates from an unsorted linked list.

FOLLOW UP

How would you solve this problem if a temporary buffer is not allowed?

译文：

从一个未排序的链表中移除重复的项

进一步地，

如果不允许使用临时的缓存，你如何解决这个问题？

【分析】

（1）如果可以使用额外的存储空间，我们就开一个数组来保存一个元素的出现情况。 对于这种情况，最好的解决方法当然是使用哈希表，但令人非常不爽的是C++标准里是没有 哈希表的(java里有)。所以，在这用一个数组模拟一下就好了。但，这里要注意一个问题， 就是元素的边界，比如链表里存储的是int型变量。那么，如果有负值，这个方法就不奏效 了。而如果元素里的最大值非常大，那么这个数组也要开得很大，而数组中大部分空间是用 不上的，会造成空间的大量浪费。

简言之，如果可以用哈希表，还是用哈希表靠谱。

如下代码遍历一遍链表即可，如果某个元素在数组里记录的是已经出现过， 那么将该元素删除。时间复杂度O(n):

如果不允许使用临时的缓存(即不能使用额外的存储空间)，那需要两个指针，cur做正常的迭代，runner指针遍历cur指针之前的所有元素，判断当前元素的值是否已经出现过。如果出现过就删除cur指向的元素。

【代码一】

/*********************************
*   日期：2014-05-17
*   作者：SJF0115
*   题目: Set Matrix Zeroes
*   来源：CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

#define N 100000

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

bool Hash[N];

ListNode* DeleteDuplicatesFromUnSortedList(ListNode *head) {
    if(head == NULL || head->next == NULL){
        return head;
    }
    memset(Hash,0,sizeof(Hash));
    ListNode* pre = head;
    ListNode* cur = head->next;

    while(cur != NULL){
        //存在重复元素删除
        if(Hash[cur->val]){
            ListNode* node = cur;
            pre->next = cur->next;
            cur = cur->next;
            delete node;
        }
        else{
            Hash[cur->val] = true;
            pre = cur;
            cur = cur->next;
        }
    }
    return head;
}

int main(){
    int i,j;
    //freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
    ListNode *head = (ListNode*)malloc(sizeof(ListNode));
    head->next = NULL;
    ListNode *node;
    ListNode *pre = head;

    int A[] = {6,5,3,3,6,5,6,7,3,7,1,2,1,4,6,7,2,3};

    for(int i = 0;i < 18;i++){
        node = (ListNode*)malloc(sizeof(ListNode));
        node->val = A[i];
        node->next = NULL;
        pre->next = node;
        pre = node;
    }

    head = DeleteDuplicatesFromUnSortedList(head);

    ListNode* cur = head->next;
    while(cur != NULL){
        printf("%d ",cur->val);
        cur = cur->next;
    }
    return 0;
}

【代码二】

/*********************************
*   日期：2014-05-17
*   作者：SJF0115
*   题目: Set Matrix Zeroes
*   来源：CareerCup
**********************************/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

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

ListNode* DeleteDuplicatesFromUnSortedList(ListNode *head) {
    if(head == NULL || head->next == NULL){
        return head;
    }
    ListNode* pre = head;
    ListNode* cur = head->next;
    //删除重复元素
    while(cur != NULL){
        ListNode* runner = head->next;
        //判断是否是重复
        while(runner != cur){
            if(runner->val == cur->val){
                ListNode* node = cur;
                //删除node
                pre->next = cur->next;
                cur = pre->next;
                delete node;
                break;
            }
            runner = runner->next;
        }
        //如果上面没有删除元素,需要更新指针
        if(runner == cur){
            pre = cur;
            cur = cur->next;
        }
    }
    return head;
}

int main(){
    int i,j;
    //freopen("C:\\Users\\XIAOSI\\Desktop\\acm.txt","r",stdin);
    ListNode *head = (ListNode*)malloc(sizeof(ListNode));
    head->next = NULL;
    ListNode *node;
    ListNode *pre = head;

    int A[] = {6,5,3,3,6,5,6,7,3,7,1,2,1,4,6,7,2,3};
    //输入
    for(int i = 0;i < 18;i++){
        node = (ListNode*)malloc(sizeof(ListNode));
        node->val = A[i];
        node->next = NULL;
        pre->next = node;
        pre = node;
    }
    //删除重复元素
    head = DeleteDuplicatesFromUnSortedList(head);
    //输出
    ListNode* cur = head->next;
    while(cur != NULL){
        printf("%d ",cur->val);
        cur = cur->next;
    }
    return 0;
}