用单链表保存 m 个整数，结点的结构为，且 |data|≤n （ n 为正整数）。现要求设计一_

[数据结构 P2080] 用单链表保存 m 个整数，结点的结构为，且 |data|≤n （ n 为正整数）。现要求设计一

学习人数: 687

正确率: 100%

题目描述

未通过

用单链表保存 m 个整数，结点的结构为，且 |data|≤n （ n 为正整数）。现要求设计一个时间复杂度尽可能高效的算法，对于链表中 data 的绝对值相等的结点，仅保留第一次出现的结点而删除其余绝对值相等的结点。例如，若给定的单链表 head 如下：

则删除结点后的 head 为：

要求：

⑴ 给出算法的基本设计思想。

⑵ 使用C或C++语言，给出单链表结点的数据类型定义。

⑶ 根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

⑷ 说明你所设计算法的时间复杂度和空间复杂度。

上一题

下一题

加入错题本

个人笔记

已有1条笔记

登录后提交答案

暂无评论，来抢沙发

参考答案

方法一：散列表

题目要求&l...

用户登录可进行刷题及查看答案

方法一：散列表

题目要求“时间复杂度尽可能高效”，所以可以考虑用散列表进行辅助。

算法基本思想如下：

从链表第一个元素开始遍历链表：

如果散列表中没有绝对值为当前元素绝对值的记录，保留该结点，并在散列表中记录当前元素绝对值，继续检查下一个结点。

如果散列表中已经有绝对值为当前元素绝对值的记录，删除该结点，继续检查下一个结点。

直到链表遍历结束。

C代码如下（含测试用例）：

C语言没有散列表这种数据结构，可以考虑用数组代替，由题目条件 |data|≤n ，只需要开辟一个大小为 n+1 的辅助数组。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int data;
    struct ListNode* link;
};

struct ListNode* deleteDuplicates(struct ListNode* head, int n) {
    int st[n + 1];
    memset(st, 0, sizeof(st));
    struct ListNode *prev = head;
    struct ListNode *curr = head->link;
    while (curr != NULL) {
        if (st[abs(curr->data)] == 1) {
            prev->link = curr->link;
            struct ListNode *temp = curr;
            curr = curr->link;
            free(temp);
        } else {
            st[abs(curr->data)] = 1;
            prev = prev->link;
            curr = curr->link;
        }
    }
    return head;
}

struct ListNode* createLinkedList(int *a, int n) {
    struct ListNode* head = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode* tail = head;
    for (int i = 0; i < n; i++) {
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->data = a[i];
        node->link = NULL;
        tail->link = node;
        tail = tail->link;
    }
    return head;
}

int main(int argc, const char * argv[]) {
    int a[] = {21, -15, -15, -7, 15};
    struct ListNode* head = createLinkedList(a, 5);
    struct ListNode* newhead = deleteDuplicates(head, 32);
    struct ListNode* curr = head->link;
    printf("head");
    while (curr != NULL) {
        printf("->%d", curr->data);
        curr = curr->link;
    }
    return 0;
}

复杂度分析

时间复杂度： O(m+n) ，初始化辅助数组时间为 O(n) ，只需要遍历一次链表，时间为 O(m) 。
空间复杂度： O(n) ，辅助数组空间为 O(n) 。

C++代码如下（含测试用例）：

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

struct ListNode {
    int data;
    ListNode *link;
};

ListNode* deleteDuplicates(ListNode* head, int n) {
    vector<int>st(n + 1);
    ListNode *prev = head;
    ListNode *curr = head->link;
    while (curr) {
        if (st[abs(curr->data)]) {
            prev->link = curr->link;
            ListNode *temp = curr;
            curr = curr->link;
            delete temp;
        } else {
            st[abs(curr->data)] = 1;
            prev = prev->link;
            curr = curr->link;
        }
    }
    return head;
}

ListNode* createLinkedList(vector<int> nums) {
    ListNode* head = new ListNode();
    ListNode* tail = head;
    for (int i = 0; i < nums.size(); i++) {
       ListNode* node = new ListNode();
        node->data = nums[i];
        node->link = nullptr;
        tail->link = node;
        tail = tail->link;
    }
    return head;
}

int main(int argc, const char * argv[]) {
    vector<int>nums{21, -15, -15, -15, -7, 15, 15};
    ListNode* head = createLinkedList(nums);
    ListNode* newhead = deleteDuplicates(head, 32);
    ListNode* curr = newhead->link;
    cout << "head";
    while (curr) {
        cout << "->" << curr->data;
        curr = curr->link;
    }
    return 0;
}

复杂度分析

时间复杂度： O(m+n) ，初始化辅助数组时间为 O(n) ，只需要遍历一次链表，时间为 O(m) 。
空间复杂度： O(n) ，辅助数组空间为 O(n) 。

虽然C++的标准函数库提供了具有散列表功能的数据结构如unordered_set和unordered_map，但首选仍然是用数组代替散列表，unordered_set和unordered_map不到迫不得已的情况不考虑使用，散列表适用于元素稀疏离散或元素范围未知的情况。C语言没有提过散列表，可以采用三方开源uthash。

C代码如下（含测试用例）：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "uthash.h"

struct ListNode {
    char data;
    struct ListNode* link;
};

struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable* find(int ikey) {
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable, &ikey, tmp);
    return tmp;
}

void insert(int ikey, int ival) {
    struct hashTable* it = find(ikey);
    if (it == NULL) {
        struct hashTable* tmp = malloc(sizeof(struct hashTable));
        tmp->key = ikey, tmp->val = ival;
        HASH_ADD_INT(hashtable, key, tmp);
    } else {
        it->val = ival;
    }
}

struct ListNode *deleteDuplicates(struct ListNode* head) {
    hashtable = NULL;
    struct ListNode *prev = head;
    struct ListNode *curr = head->link;
    while (curr) {
        struct hashTable *it = find(abs(curr->data));
        if (it != NULL) {
            prev->link = curr->link;
            struct ListNode *temp = curr;
            curr = curr->link;
            free(temp);
        } else {
            insert(abs(curr->data), 1);
            prev = prev->link;
            curr = curr->link;
        }
    }
    return head;
}

struct ListNode* createLinkedList(int *a, int n) {
    struct ListNode* head = (struct ListNode *)malloc(sizeof(struct ListNode));
    struct ListNode* tail = head;
    for (int i = 0; i < n; i++) {
        struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
        node->data = a[i];
        node->link = NULL;
        tail->link = node;
        tail = tail->link;
    }
    return head;
}

int main(int argc, const char * argv[]) {
    int a[] = {21, -15, -15, -7, 15};
    struct ListNode* head = createLinkedList(a, 5);
    struct ListNode* newhead = deleteDuplicates(head);
    struct ListNode* curr = head->link;
    printf("head");
    while (curr != NULL) {
        printf("->%d", curr->data);
        curr = curr->link;
    }
    return 0;
}

C++代码如下（含测试用例）：

#include <iostream>
#include <unordered_set>
#include <vector>
using namespace std;

struct ListNode {
    int data;
    ListNode *link;
};

ListNode* deleteDuplicates(ListNode* head) {
    unordered_set<int>st;
    ListNode *prev = head;
    ListNode *curr = head->link;
    while (curr) {
        if (st.count(abs(curr->data))) {
            prev->link = curr->link;
            ListNode *temp = curr;
            curr = curr->link;
            delete temp;
        } else {
            st.insert(abs(curr->data));
            prev = prev->link;
            curr = curr->link;
        }
    }
    return head;
}

ListNode* createLinkedList(vector<int> nums) {
    ListNode* head = new ListNode();
    ListNode* tail = head;
    for (int i = 0; i < nums.size(); i++) {
       ListNode* node = new ListNode();
        node->data = nums[i];
        node->link = nullptr;
        tail->link = node;
        tail = tail->link;
    }
    return head;
}

int main(int argc, const char * argv[]) {
    vector<int>nums{21, -15, -15, -15, -7, 15, 15};
    ListNode* head = createLinkedList(nums);
    ListNode* newhead = deleteDuplicates(head);
    ListNode* curr = newhead->link;
    cout << "head";
    while (curr) {
        cout << "->" << curr->data;
        curr = curr->link;
    }
    return 0;
}

复杂度分析

时间复杂度： O(m) ，只需要遍历一次链表。
空间复杂度： O(m) ，辅助散列表空间为 O(m) 。