文章524
标签277
分类67

算法:链表中倒数第k个结点


链表中倒数第k个结点

链表中倒数第k个结点

输入一个链表,输出该链表中倒数第k个结点。


分析

明显的快慢指针的问题

先让快指针走k步, 然后慢指针和快指针同时走, 当快指针到结尾之后, 慢指针即为第k个.

难点在于k的大小可能超过了链表长度, 此时fast指针会提前结束, 所以要在fast开始前进时进行判断:

1
2
3
4
while (fast != null && --k >= 0) {
fast = fast.next;
}
if (fast == null) return k == 0 ? slow : null;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if (head == null || k <= 0) return null;

ListNode fast = head, slow = head;
while (fast != null && --k >= 0) {
fast = fast.next;
}
if (fast == null) return k == 0 ? slow : null;

while (fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}

本文作者:Jasonkay
本文链接:https://jasonkayzk.github.io/cn/1996/07/27/%E7%AE%97%E6%B3%95-%E9%93%BE%E8%A1%A8%E4%B8%AD%E5%80%92%E6%95%B0%E7%AC%ACk%E4%B8%AA%E7%BB%93%E7%82%B9/
版权声明:本文采用 CC BY-NC-SA 3.0 CN 协议进行许可