【第三轮】6.23-6.29 CareerCup 2.1

2.1
Write code to remove duplicates from an unsorted linked list.
FOLLOW UP
How would you solve this problem if a temporary buffer is not allowed?

回复解法可以按照以下格式来

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link】
---------------Optional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Notice：
1、记得在程序注释中表明自己算法的时间、空间复杂度
2、代码难懂之处加注释
3、每道题目有对应的帖子，除了贴解法，欢迎讨论，集思广益
4、任何未尽之处，欢迎回报名帖提问，我会进一步作出修改。

【解题思路】
Use hash table to record elements showed up earlier, removed node if it shows up again later.
Follow up: for each node, scan through all of its following nodes and remove duplicates;

【时间复杂度】
O(N)
Follow up: O(N^2)

【空间复杂度】
O(N)
Follow up: O(1)

【gist link】
https://gist.github.com/chrislukkk/fc2ce325c06ab6e47c1e

【解题思路】
1. 用hash set：建立一个hash set，并遍历链表。如果链表的点在hash set里面，则删除这个点；如果不在的话，插入到hash set里。
2. 不用hash set：两个指针，第一个current就正常遍历链表；第二个runner每一次都遍历current之前的，并查找重复的。如果有，则current所指向的。
3. 需要注意的是，删除current的时候并不能直接删除，因为需要让current之前的那一个的next指向current之后的那一个。所以我们让current永远指向当前node的前一个即可。
【时间复杂度】
用hash set: O(n)
不用hash set: O(n^2)
【空间复杂度】
用hash set: O(n)? (其实一直不知道时候hash table / hash set的时候，空间复杂度怎么算，求指点)
不用hash set: O(1)
【gist link】
https://gist.github.com/seemuch/af64b140e576b6ea73ad#file-2_1-cc
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

【解题思路】HashSet，遇到不重复的，添加进LinkedList，最后返回LinkedList。不允许用buffer的话，用brute force求解。
也考虑过先用quicksort，但是single linkedlist的交换不能做到array里面的O(1)，并且two-way quicksort在应付[a,a,a,a,a,a]这种重复元素很多的数组时，复杂度接近于O(n^2)。3-way quicksort可以解决这个问题，但是算法里需要头尾两个指针依次向中间移动，而single linkedlist不能回溯到前一个元素。
【时间复杂度】O(n) / O(n^2)
【空间复杂度】O(n) / O(1)
【gist link】
HashSet: https://gist.github.com/chouclee/eba793a770b25674ad78
Brute-force： https://gist.github.com/chouclee/fddce83f4860442aa333

【解题思路】
1. If the data of each node comes from a fixed character set like ASCII, we can create a array to store whether the character appear in the string. Thus, runtime is O(n), space is O(size of character set). If we don't know the range of data, we can use hashtable.
2. If the space must be O(1), we can search each character in the string, runtime time is O(n^2).
【时间复杂度】
1. O(n)
2. O(n^2)
【空间复杂度】
1. O(n)
2. O(1)
【gist link】
https://gist.github.com/qianhuang/fa817dd6f55c5c21aa39

【解题思路】
three pointers
【时间复杂度】
n2
【空间复杂度】
1
【gist link】
https://gist.github.com/gaoyike/badaff09f773e2a7707e


弱爆了我
---------------OPTional，如果觉得test case比较好，欢迎写出来分享----------------------
【test case】

Solution              : I am gonna sort the linked list first, and check value one by one, and reconnect the link and free the duplicate node
Time Complexity  : O(n^2)
Space Complexity : O(n)
Gist Link              : https://gist.github.com/habina/3896531754d629b2032f

【解题思路】
第一步很简单想到用各种hash来去掉重复值。
follow up的就是在链表中一个一个对照的去掉重复值。
P.S. Test Case各种写不好。。直接参考一楼了  0 0

【时间复杂度】
O(N)
Follow up: O(N^2)

【空间复杂度】
O(N)
Follow up: O(1)

【gist link】
https://gist.github.com/UncleGarden/55470d66c3823ce9144e

【解题思路】
Hashmap
直接o（n2）的复杂度，循环比较

【时间复杂度】
O(N)
Follow up: O(N^2)

【空间复杂度】
O(N)
O(1)

【gist link】
https://gist.github.com/qiangusc/38a45fa1b39a0185b31a