【第四轮】4.6 - 4.12 Career Cup 2.1

【解题思路】
With extra buffer: use a hashmap to store the element and  remove the dup if it already exists in the hashmap
Without extra buffer: use two pointers, one to indicate the current element, one to iterate through the rest of the linkedlist to remove dup.
【时间复杂度】O(N) or O(N^2)
【空间复杂度】O(N) or O(1)
【gist link] https://gist.github.com/kelly-us/2aa0e810fa70696fb056

[solution 1]
use a hashset to store elements that occurred, delete the current element if it's included in the hashset.
[time]
O(n)
[space]
O(n)

[solution 2]
for each current element, test each element after it, delete the ones that is same with current element
[time]
O(n^2)
[space]
O(1)

[gist]
https://gist.github.com/A30041839/5514a3bc3e738db22054

【解题思路】
  1. 用hashtable 存数据，遇到重复的就删除。
  2. 两个指针前后扫一边
【时间复杂度】
1. O(n), 2.O(n^2)
【空间复杂度】
1. O(n) 2. O(1)
【gist link]
https://gist.github.com/songpu2015617/767122161cdf0f583ddc
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

【解题思路】   1. Use hashtable to store the data element for visited nodes, compare newly visted node
        to see if its data is already in the table. If yes, remove the duplicate, else add its data
        into the table.

   2(No temporary buffer). Use two pointers for two layers iteration.
【时间复杂度】 O(n) for 1, O(n^2) for 2
【空间复杂度】O(n) for 1, O(1) for 2
【gist link] https://github.com/StephenWeiXu/ ... aster/Chap2/2_1.cpp
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

【解题思路】
Go through the linked list, if it's a new value, then store it in a hashtable. If it already exists in the hashtable, then skip the node.
Using dummy head makes it easier to code.
   
【时间复杂度】
O(N)
【空间复杂度】
O(N)

Code link
https://gist.github.com/mogutou1214/e5a233231944ad32b50d

coperdli 发表于 2015-4-10 09:37
解题思路：目前只想到一种糟糕的方法，当遍历整个链表时，将剩余链表部分钟与当前元素值相同的节点统统从链 ...

请问一下这个题怎么用排序做？排序完后，原始linked list的结构就变了再去remove的话能行吗？