求链表的倒数第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回答

liuyubobobo

2018-06-18

扫下来,至少空链表的判断有问题。Leetcode上的问题传入的链表应该默认都没有虚拟头结点的。所有空链表是head == null 而不是 head.next == null。如果传来的head是空,在空链表判断那一行会报空指针异常:)


下次询问Leetcode的问题请附上题号哦:)谢谢!

0
0

玩转数据结构

动态数组/栈/队列/链表/BST/堆/线段树/Trie/并查集/AVL/红黑树…

6221 学习 · 1704 问题

查看课程