题目描述
输入一个链表，输出该链表中倒数第k个结点。
解题思路一
将所有结点值存入容器，直接用索引值找到结果结点,时间复杂度O(n) ,空间复杂度O(n)
/**
* 时间复杂度O(n) ,空间复杂度O(n)
*
* @param head
* @param k
* @return
*/
public ListNode FindKthToTail(ListNode head, int k) {
if (head == null || k == 0)
return null;
//方法一，建立辅助空间arrayList存放所有结点
List<ListNode> list = new ArrayList<ListNode>();
while (head != null) {
list.add(head);
head = head.next;
}
if (Math.abs(k) > list.size())
return null; //k值超出有效范围
//对K进行处理，取余
if (k < 0) {
//倒数负数个也即是正序取第几个
return list.get(Math.abs(k) - 1);
} else {
return list.get(list.size() - k);
}
}
解题思路二
建立长度为K的滑窗，然后向右移动，直至滑窗右边界达到终点，那么滑窗左边界为所求,时间复杂度O(n)，空间复杂度O(1)
public ListNode FindKthToTail2(ListNode head, int k) { //时间复杂度O(n)，空间复杂度O(1)
if (head == null || k <= 0)
return null;
//创建滑窗，大小为K，不停向右移动，直到窗口右端到达边界，左端就是倒数K个
ListNode left = head;
ListNode right = head;
//让right移动k-1个，创建滑窗
while (k > 1){
right = right.next;
k --;
if(right == null){
//链表长度小于K，错误
return null;
}
}
//[left..right]同时向右移动
while (right.next != null){
left = left.next;
right = right.next;
}
return left;
}
