首页 > 试题广场 >

删除无序链表中值重复出现的节点

[编程题]删除无序链表中值重复出现的节点

热度指数：1666 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个无序链表，删除其中值重复出现的节点(保留当中顺序遍历第一个出现的节点)。

输入描述:

第一行一个整数 n，表示单链表的节点数量。
第二行 n 个整数表示单链表的节点的值。

输出描述:

顺序输出单链表每个节点的值。

示例1

输入

5
1 3 2 3 1

输出

1 3 2

备注:

算法知识视频讲解

pein531

不考虑空间复杂度的话还是比较容易实现O(n)时间复杂度的，直接重构一个链表就行：

遍历原始链表，并用一个集合记录已经出现过的节点值，如果当前值已经出现过，就直接跳过，否则创建一个新的节点追加在当前链表的后面。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashSet;

class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val) {
        this.val = val;
        this.next = null;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String[] strList = br.readLine().trim().split(" ");
        ListNode head = new ListNode(Integer.parseInt(strList[0]));
        ListNode cur = head;
        for(int i = 1; i < n; i++){
            cur.next = new ListNode(Integer.parseInt(strList[i]));
            cur = cur.next;
        }
        head = removeDuplicates(head, n);
        while(head != null){
            System.out.print(head.val + " ");
            head = head.next;
        }
    }
    
    private static ListNode removeDuplicates(ListNode head, int len) {
        ListNode cur = head;
        HashSet<Integer> set = new HashSet<>();
        ListNode newHead = new ListNode(head.val);
        ListNode newCur = newHead;
        while(cur != null){
            if(!set.contains(cur.val)){
                set.add(cur.val);
                newCur.next = new ListNode(cur.val);
                newCur = newCur.next;
            }
            cur = cur.next;
        }
        return newHead.next;     // 注意头结点重复了一次，直接跳过
    }
}

编辑于 2021-06-07 17:32:14 回复(0)

张嘉麟

#include <iostream>
#include<stack>
#include<vector>
#include<algorithm>
#include<list>
#include<unordered_map>
using namespace std;
//链表节点结构体
struct ListNode {
    int val;
    ListNode* next;
    ListNode():val(0),next(nullptr){}
    ListNode(int x):val(x),next(nullptr){}
    ListNode(int x,ListNode* next):val(x),next(next){}
};
//初始化插入数据
ListNode* Init() {
    ListNode* head=new ListNode(-1);
    ListNode* tmp=head;
    int n;
    int x;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        ListNode* newNode = new ListNode(x);
        tmp->next = newNode;
        tmp = tmp->next;
    }
    return head->next;
}
//打印链表
void PrintList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
}

class Solution {
public:
    Solution() {
    }
    //哈希表
    ListNode* Hash(ListNode* head) {
        ListNode* res = new ListNode(-1);
        ListNode* cur = res;
        unordered_map<int, int> map;
        while (head != nullptr) {
            map[head->val]++;
            if (map[head->val] == 1) {
                ListNode* newNode = new ListNode(head->val);
                cur->next = newNode;
                cur = cur->next;
            }
            head = head->next;
        }
        return res->next;
    }
    
};

int main() {
    Solution s;
    ListNode* p = Init();
    ListNode* res=s.Hash(p);
    PrintList(res);
    return 0;
}

发表于 2024-04-02 17:28:22 回复(0)

天蓬源帅11

#include <iostream>
#include <unordered_map>
using namespace std;

struct ListNode
{
    int val;
    ListNode* next;
    ListNode() : val(-1), next(nullptr){}
    ListNode(int val) : val(val), next(nullptr){}
};

int main() {
    ListNode* dummyHead = new ListNode();
    ListNode* p = dummyHead;
    int n;
    cin >> n;
    while (n--)
    {
        int v;
        cin >> v;
        p->next = new ListNode(v);
        p = p->next;
    }

    p = dummyHead->next;
    ListNode* pre = dummyHead;
    unordered_map<int, int> count;
    
    while (p != nullptr)
    {
        if (count[p->val] == 1)
        {
            pre->next = p->next;
            p = pre->next;
        }
        else
        {
            ++count[p->val];
            pre = p;
            p = p->next;
        }
    }
    p = dummyHead->next;
    while (p != nullptr)
    {
        cout << p->val << " ";
        p = p->next;
    }

    return 0;
    
}
// 64 位输出请用 printf("%lld")

发表于 2023-08-30 14:46:19 回复(0)

Python 3

毓毓子最可爱

n=input()
number_lsit=list(map(int,input().split()))
ans=[]
#利用集合去重
table=set()
for i in number_lsit:
    if i not in table:
        ans.append(i)
        table.add(i)
print(" ".join(map(str,ans)))

发表于 2021-09-07 09:10:11 回复(0)

程序猿的浪漫

list_node * remove_rep(list_node * head)
{
    //////在下面完成代码
    map<int,int>mp;
    mp[head->val] = 1;
    list_node* ans = head;
    list_node* cur = head->next;
    while(cur != nullptr){
        if(mp[cur->val] == 0){
            head->next = cur;
            head = cur;
            mp[cur->val]++;
        }
        cur = cur->next;
    }
    head->next = nullptr;
    return ans;
}

发表于 2020-07-08 21:14:03 回复(0)

加油北鼻

list_node * remove_rep(list_node * head)
{
    //////在下面完成代码
    set <int> numFlag;
    list_node* pNode = head;
    list_node* pre = nullptr;
    while (pNode != nullptr)
    {
        if (numFlag.count(pNode->val) == 0)
        {
            numFlag.insert(pNode->val);
            pre = pNode;
            pNode = pNode->next;

        }
        else
        {
            pre->next = pNode->next;
            pNode = pNode->next;
        }
    }
    return head;

}

发表于 2020-07-03 20:14:50 回复(0)

EVANnnn1996

两种方法：方法一时间复杂度 O(N)，额外空间复杂度 O(N)；方法二时间复杂度 O(N^2)，额外空间复杂度 O(1)。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;

public class Main {
    
    public static class Node {

        public int value;
        public Node next;

        public Node(int value) {
            this.value = value;
        }
    }
    
    public static Node listGenerator(int length, String[] numbers) {
        Node head = new Node(Integer.parseInt(numbers[0]));
        Node cur = head;
        for (int i = 1; i < length; i++) {
            cur.next = new Node(Integer.parseInt(numbers[i]));
            cur = cur.next;
        }
        cur.next = null;
        return head;
    }
    
    public static void printList(Node head) {
        while (head != null) {
            System.out.print(head.value +" ");
            head = head.next;
        }
        System.out.println();
    }
    
    public static void removeRep1(Node head) {
        if (head == null || head.next == null) {
            return;
        }
        HashSet<Integer> hashSet = new HashSet<>();
        hashSet.add(head.value);
        Node pre = head;
        Node cur = head.next;
        while (cur != null) {
            if (hashSet.contains(cur.value)) {
                pre.next = cur.next;
            } else {
                hashSet.add(cur.value);
                pre = cur;
            }
            cur = cur.next;
        }
    }

    public static void removeRep2(Node head) {
        if (head == null || head.next == null) {
            return;
        }
        Node each = head;
        Node pre;
        Node cur;
        while (each != null) {
            pre = each;
            cur = each.next;
            while (cur != null) {
                if (cur.value == each.value) {
                    pre.next = cur.next;
                } else {
                    pre = cur;
                }
                cur = cur.next;
            }
            each = each.next;
        }
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bufferedReader.readLine());
        String[] numbers = bufferedReader.readLine().split(" ");
        Node head = listGenerator(n, numbers);
        removeRep1(head);
        printList(head);
    }
}

发表于 2020-02-12 21:39:17 回复(0)

Ewin

list_node * remove_rep(list_node * head)
{
    //面完成代码
    set<int> tmp;
    list_node * cur = head;
    list_node * last;
    while(cur!=nullptr){
        if(tmp.count(cur->val)==0){
            tmp.insert(cur->val);
            last = cur;
            cur = cur->next;
        }else{
            last->next = cur->next;
            cur = last->next;
        }
              
    }
    return head;


}

发表于 2019-08-26 18:44:57 回复(0)