移除链表的重复节点要求时间复杂度低一点的

Question

移除未排序链表中的重复节点。保留最开始出现的节点。

力扣 https://leetcode-cn.com/problems/remove-duplicate-node-lcci/

Answer 1

一、源码

int hash[100010];

struct ListNode* removeDuplicateNodes(struct ListNode* head){
    int i;
    struct ListNode *pre = NULL, *now = head;
    memset(hash, 0, sizeof(hash));
    while(now) {
        if( !hash[now->val] ) {
            hash[now->val] = 1;
            pre = now;
        }else {
            pre->next = now->next;
        }
        now = pre->next;
    }
    return head;
}

二、解释

可以搞一个哈希表，记录已经出现过的结点，下次就不要加进来，然后就可以啦！