题解 | #链表中倒数最后k个结点(进阶版)#
链表中倒数最后k个结点
http://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
// 此题的进阶版:使用快慢指针,快指针领先k-1步,当快指针到达链表最后一个非null节点的时候,慢指针也就到达倒数第k个了。时间复杂度仍然是O(n),但空间复杂度变为了O(1),比用栈要好。
// 快慢指针分两种,一种是快指针领先固定步数,一种是快指针前进速度快,可以一下前进2步
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param pHead ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode FindKthToTail (ListNode pHead, int k) {
// write code here
if(k<=0)
return null;
ListNode nodeQ = pHead;
ListNode nodeS = pHead;
for(int i = 1; i < k; i++){
if(nodeQ == null || nodeQ.next == null)
return null;
else
nodeQ = nodeQ.next;
}
while(nodeQ.next != null){
nodeQ = nodeQ.next;
nodeS = nodeS.next;
}
return nodeS;
}
}