输入一个链表, 输出该链表中倒数第 k 个结点.
核心思想: 两个指针, 先让第一个指针和第二个指针都指向头结点, 然后再让第一个指正走 (k-1) 步, 到达第 k 个节点.
然后两个指针同时往后移动, 当第一个结点到达末尾的时候, 第二个结点所在位置就是倒数第 k 个节点了
时间复杂度 O(n), 一次遍历即可
- /*
- public class ListNode {
- int val;
- ListNode next = null;
- ListNode(int val) {
- this.val = val;
- }
- }*/
- import java.util.*;
- public class Solution {
- public static ListNode FindKthToTail(ListNode head,int k) {
- // 特殊情况判定
- if(head==null) return null;
- if(k<=0) return null;
- // 建立两个指针
- ListNode fastptr = head;
- ListNode slowptr = head;
- // 快的指针跑到了第 k-1 个节点处(默认第一个节点是 1 而不是 0)
- for(int i=1;i<k;i++){
- if(fastptr.next != null){
- fastptr = fastptr.next;
- }
- else return null; // 要考虑到链表长度小于 K 的情况
- }
- while(fastptr.next != null){
- fastptr = fastptr.next;
- slowptr = slowptr.next;
- }
- return slowptr;
- }
- public static void main(String [] args){
- Scanner sc = new Scanner(System.in);
- System.out.println("请输入倒数第几个节点");
- int k= sc.nextInt();
- System.out.println("请依次输入链表");
- ListNode head = null;
- if(sc.hasNext()) head = new ListNode(sc.nextInt());
- ListNode temp = head;
- while(sc.hasNext()){
- temp = new ListNode(sc.nextInt());
- temp = temp.next;
- }
- temp.next = null;
- ListNode result = FindKthToTail(head,k);
- System.out.println("该链表的倒数第 k 个节点是"+ result);
- }
- }
调试中出现的 bug
bug1: 没有考虑到 K 为负数或者 K 为 0 的情况, 没有考虑 head 为空的情况, 添加了 13 和 14 行代码
bug2: 没有考虑 K 远远大于链表长度的时候, 可以选择将 K 和链表 length 做比较, 此时需要再写一个 length 函数, 比较费劲
或者可以用来解决这种情况, 注意此处是 fastptr.next 而不是 fastptr
- for(int i=1;i<k;i++){
- if(fastptr.next != null){
- fastptr = fastptr.next;
- }
- else return null;
bug3: 在 IDEA 判断链表输入何时结束出了问题, 而牛客网不用输入结束条件
图片参考来自于:
在 IDEA 中需要将主函数改为:
来源: http://www.bubuko.com/infodetail-3109685.html