【第四轮】4.6 - 4.12 Career Cup 2.2

2.2 Implement an algorithm to find the kth to last element of a singly linked list.

请参加活动的童鞋跟帖回复自己的解法，回复请参考以下格式：

【解题思路】
【时间复杂度】
【空间复杂度】
【gist link]
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

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

【解题思路】快慢指針，基於這個數學推導過程，kth-to-last = len - k，先向前走k，然後兩個同時走，當快指針走到底的時候，慢指針就是目標元素
【时间复杂度】O(N)
【空间复杂度】O(1)
【gist link]  https://github.com/noisedispatch/CC150/blob/master/src/main/java/chap2/FindKth2Last.java
【test case】
https://github.com/noisedispatch/CC150/blob/master/src/test/java/chap2/TestFindKth2Last.java

看了上面同學的代碼，想到一個測試用例是如果輸入的 k 是一個非法的數字，比如說鏈表長度為10，而 k 是20，那麽這個時候一定要處理，否則會有異常。

此外是我自己的一個錯誤，就是在移動指針之前，一定要保證當前指針不為空才行，這個錯誤是在測試返回 head 元素時發現的。

【解题思路】
* First we need to know if there are k elements in the list,
* if not return nothing.
*
* After we find the kth element from the beginning, we create
* a new pointer pointing at the head, so the distance between
* old pointer and new pointer is `k`. Then we move them
* simultaneously until the old pointer reaches the end of the list.
* Then we get the last k elements in the list.
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link] https://github.com/bxshi/intervi ... to_last_element.cpp
【test case】(optional，如果觉得比较好，欢迎贴出来分享）https://github.com/bxshi/intervi ... c/test/2_2_test.cpp

【解题思路】Iterative methods - use two pointers, one is kth ahead of the other one. Then forward these
        two pointers with the same pace. When the first pointer reach the end, the second pointer
        will point to the kth element to the last element
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link] https://github.com/StephenWeiXu/ ... aster/Chap2/2_2.cpp
【test case】(optional，如果觉得比较好，欢迎贴出来分享）

【解题思路】
use two pointers  first pointer  move k times  then  move first and second  pointer  together   until first reach  the end
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link]
https://gist.github.com/michaelniu/d81729783fdeff6ee48c
【test case】
https://gist.github.com/michaelniu/d81729783fdeff6ee48c  (main)

【解题思路】
这个题思路大家应该都比较一致，就是用快慢指针来做
【时间复杂度】
O（n）
【空间复杂度】
O(1)
【gist link]
https://github.com/JamesJi9277/C ... inkedLists/2.2.java
【test case】

解题思路】
用快慢指针，如果快指针并检查k是否大于list的长度。
【时间复杂度】O(n)
【空间复杂度】O(1)
【gist link]
https://github.com/chongtianzs/CC150/blob/master/2.2-cc150.cpp

【解题思路】
快慢指针
【时间复杂度】
O(n)
【空间复杂度】
O(1)
【gist link】
https://gist.github.com/alikewmk ... -2-findktolast-java

思路：遍历链表，得出总的元素个数，由此可计算得到所求元素距离链表头部的距离，然后从头部开始搜索特定距离便可得
时间复杂度：O(n)
空间复杂度：O(1)
code snippet & test: https://gist.github.com/coperd/4ac2f0573b55e4210667

补充内容 (2015-5-4 20:30):
考虑了各位所说的哈希方法，但是在本题中不知道数据特征的情况下，如何用hash？例如，数据全是整形，那选取hash函数: f(i) = i（就是直接将链表数据映射为下标）; 则哈希表的大小为max(num in list).

【解题思路】
1.使用static variable存count, 然后recursive调用函数。

【时间复杂度】
1.O(n)

【空间复杂度】
1.O(n)

【gist link】        Java
https://gist.github.com/LinyinWu/1013d20adbcd1ac39cbd
【test case】
"FOLLOWuuP" k=4        --->        "W"

干.什么 发表于 2015-4-13 07:12
【解题思路】快慢指針，基於這個數學推導過程，kth-to-last = len - k，先向前走k，然後兩個同時走，當快指 ...

這裏是鏈接地址：

Source Code: https://github.com/noisedispatch/CC150/blob/master/src/main/java/chap2/FindKth2Last.java

Test Case: https://github.com/noisedispatch/CC150/blob/master/src/test/java/chap2/TestFindKth2Last.java

誰能教教我怎麼插入超級鏈接，每次都失敗