[第二轮] 2/25-3/3 CareerCup 2.2

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

发帖规范:
http://www.1point3acres.com/bbs/thread-48094-1-1.html
http://www.1point3acres.com/bbs/thread-32423-1-1.html

Use two "pointers" iterate through the linked list, the second one lags behind the first one by k position.
Runtime complexity O(N), storage complexity O(1).
https://gist.github.com/Zuohr/5023018

https://github.com/starcroce/car ... r/careercup_2_2.cpp
本来想法很直接，先遍历一遍拿到长度再去找倒数第k个，然后看了一楼的算法之后重新改了下。。。
先看k和head合不合法，然后就设两个相距k的指针往后移，一个到底了另一个也就到倒数k个了。。。

https://gist.github.com/njcongtou/4999347

1。 use two pointers, k interval between them.

Same as ls
https://gist.github.com/mazl123321/5024165

刚开始看成kth largest element to the end..
kth element的话，一样是两个pointer，tracking down to the end of the list
https://gist.github.com/chrislukkk/5023048/edit

刚开始看成kth largest element to the end..
kth element的话，一样是两个pointer，tracking down to the end of the list
https://gist.github.com/chrislukkk/5023048/edit

这道题二楼所说的那种做法，先遍历一遍拿到长度再去找倒数第k个，比答案差在哪里呢？
谢谢！

mapleman 发表于 2013-2-25 02:10
这道题二楼所说的那种做法，先遍历一遍拿到长度再去找倒数第k个，比答案差在哪里呢？
谢谢！

时间复杂度都是O(n)，但是改进后的做法只需要遍历一遍，我的最初想法相当于遍历两遍，所以改进后常数项上做了点优化。。。

https://gist.github.com/mettaworld/5028492
java language
find the kth node with a loop, then output the nodes from kth to the last with a loop