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

https://gist.github.com/ThunderXu/5029766
1. make two pointer: former and later, former points to the head and later points to the kth element;
2. move two pointers to the end, when later arrives the end, start outputing elements that former points to until it also arrives the end.

https://github.com/quantumrose/C ... /2.2.KthToLast.java

method1: first traverse the linked list to get its length, then find the kth to last element. O(n) time, O(1) space
method2: use two pointers k nodes apart and move them together. O(n) time, O(1) space
method3: recursive. O(n) time, O(n) space
不太明白这题用recursive的优势在哪里......

zuohr 发表于 2013-2-24 15:36
Use two "pointers" iterate through the linked list, the second one lags behind the first one by k po ...

Brilliant idea!

grassgigi 发表于 2013-2-25 01:18
刚开始看成kth largest element to the end..
kth element的话，一样是两个pointer，tracking down to the ...

Me too! if it's indeed to find the kth largest element, then I think we have to read all the values in to memory first. This is the only method I know to solve this alternate problem, maybe you and other smart guy can figure out a much more efficient way

https://github.com/moophis/careercup/blob/master/2.2.cpp

The same with others.

starcroce 发表于 2013-2-25 04:04
时间复杂度都是O(n)，但是改进后的做法只需要遍历一遍，我的最初想法相当于遍历两遍，所以改进后常数项上 ...

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

直观的方法是一个指针遍历两遍：第一次指针遍历整个list（距离n），再返回原处，第二次遍历n-k的距离，加起来遍历的距离是2n-k
1楼的做法是用两个指针遍历一遍：一个指针遍历整个list（距离n），另一个指针遍历n-k的距离，加起来还是2n-k
我的理解是：在 k 比较小，而链表很大的时候，第二种方法能利用空间局部性，可以快一点，因此1楼的解法会比较好。

Inspired by zuohr.
* Method: Use two pointers to iterate through the list,
* the first one has k distance to the second one, when the
* second one gets to the end, return the first pointer.

C language:https://gist.github.com/hukun01/5037818

2个指针，间隔k，直到后面的指针扫到尾。
https://gist.github.com/skxie/6c18c92944d7ee609f95

gist: https://gist.github.com/sing1ee/5046004

use two pointer method when the first pointer step forward k steps, the
second pointer start to move. when the first pointer goes to the end, the
second points to the last kth element.

Move the head point to "start head point"

https://gist.github.com/lazyGoose/5048684