【第三轮】6.23-6.29 CareerCup 2.2

grassgigi 发表于 2014-6-24 09:03
【解题思路】
Runner tech

你好，我对于泛型有些不理解
public static <T> Node<T> kthToLast(MyLinkedList<T> list, int k)
这一行为什么不能直接写成
public Node<T> kthToLast(MyLinkedList<T> list, int k)
请楼主帮忙分析下，谢啦

Solution1
Idea:
1. iterate the LinkedList first, and calculate the size of the list, mark as n
2. iterate the list again until it reach the n – k element and return
3. move p1 and p2 a end of the linkedList, the p1 will be the Kth node and return the val of p1

Time Complexity: O(n)
Space Complexity: O(1)

Solution2
Idea: using two pointers
1. two pointers p1 and p2, initial set at the head of the input LinkedList
2. just move the p2 to the Kth node of the list
3. move p1 and p2 at the same space
4. when the p2 hit the end of the linkedList, the p1 will be the Kth node and return the val of p1

Time Complexity: O(n)
Space Complexity: O(1)

Code:
http://www.jyuan92.com/post-440