链表系列之 无序单链表去重
【算法专题 - 链表】
- 《》
- 《》
- 《》
【题目】 现有一个无序单链表,其中存在重复元素,实现一个算法来删除重复出现的元素,最终使得单链表中所有元素仅出现一次。
【其他限制】 无
【图示】 假设无序单链表为如下结构(蓝色): 【分析】 针对本问题,最简单的思路也即两层循环,针对每一个元素查找所有与其值相等的元素,然后删除即可,因为存在嵌套循环,故时间复杂度为O(N2)。 仔细思考,遍历查找类问题的一个行之有效的方法是合理使用哈希表。如此只需要遍历一边,遍历的过程中做好标识,即可以在遍历过程中发现重复元素,跳过重复元素即可。
【代码实现】
/* Node struct */ public Node { public int data; public Node next; public Node(int data) { this.data = data; } }
- 时间复杂度O(N2),空间复杂度O(1)
/* * DESC: * A function can remove the duplicted elememnts of a no sorted linklist */ public void removeDuplicatedElements_1(Node head) { Node cur = head; Node pre = NULL; Node next = NULL; while (NULL != cur) { pre = cur; next = cur.next; while (NULL != next) { if (cur.data == next.data) { pre.next = next.next; // Maybe you should free the resource used by pointer next here // free(next); } else { pre = next; } next = next.next; } cur = cur.next; } }
- 时间复杂度O(N),空间复杂度O(N)
public void removeDuplicatedElements_2(Node head) { if (NULL == head) return; HashSet<Integer> hash_set = new HashSet<Integer>(); Node pre = head; Node cur = head.next; hash_set.add(head.data); while (NULL != cur) { if (hash_set.contains(cur.data)) { pre.next = cur.next; } else { hash_set.add(cur.data); pre = cur; } cur = cur.next; } }