求链表的倒数第k个节点
来源:4-1 什么是链表
黎明的烬
2018-06-17
特地请教一下老师,有空的话就瞅两眼,拜托,一道算法题;不知道哪儿出错了,一直不能AC:
/**
* 输入一个链表,输出该链表中倒数第k个结点
*/
public class Main01 {
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
/**
* 快慢指针法:转化为让first指针先跑k-1步,
*
*
* @param head
* @param k
* @return
*/
public ListNode FindKthToTail(ListNode head,int k) {
ListNode first = head;
ListNode second = head;
if (head.next==null){//空列表 直接返回
return head.next;
}
if (k<1){//k小于1
return null;
}
for (int i=0;i<k-1;i++){//让first先跑k-1步,
first = first.next;
if (first==null){//当k大于链表的长度,直接返回空链表
return first;
}
}
while (first.next!=null){//first跑完需要一起跑了
first = first.next;
second = second.next;
}
return second;
}
}
1回答
-
扫下来,至少空链表的判断有问题。Leetcode上的问题传入的链表应该默认都没有虚拟头结点的。所有空链表是head == null 而不是 head.next == null。如果传来的head是空,在空链表判断那一行会报空指针异常:)
下次询问Leetcode的问题请附上题号哦:)谢谢!
00