数据结构与算法专题题库

1011. 链表去重

单点时限: 2.0 sec

内存限制: 256 MB

实现线性链表的去重操作,不需要排序,复杂度要求是$O(N^2)$。

只需完成给定函数的定义。

Node* uniqueLinklist(Node *head) {
    // TODO
}

其中

Node表示链表的结构体,定义如下

struct Node
{
    int data;
    Node *next;
};

head指向链表的头结点,如果链表为空,headNULL

你需要实现uniqueLinkedlist函数,其中head为链表的头节点。

在去重的过程中,不考虑数据的相对顺序,为了确保输出的唯一性,在判题程序中已经对数据进行排序了

样例

Input
5
3 2 2 1 1
Output
1 2 3

提示

只能用C++提交,判题程序如下:

int main()
{
    // 隐藏一些细节 
    int n;
    cin>>n;
    for (int i=0;i<n;i++)
        cin>>a[i];
    Node* head=createLinklist(a,n);
    Node* nhead=uniqueLinklist(head);
    vector <int> v; 
    Node* p=nhead;
    while (p)
    {
        v.push_back(p->data);
        p=p->next; 
    }
    sort(v.begin(),v.end());
    for (int i=0;i<v.size();i++)
        cout<<v[i]<<' ';
    cout<<endl;
    return 0;
}

在完成题目的过程中不允许使用STL,也不允许使用额外内存~

提交的代码必须包含那一个函数的实现,不需要写额外的代码(比如main函数,节点声明等等)

在实现过程中,你可以添加其他函数

如果在函数中没有声明额外数组,但是程序运行结果是Memory Limit Exceeded,请尝试多次提交。

不限期开放

题目列表