题目描述

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

 

分析：此题为常见的快慢指针问题，java实现时要注意空指针错误以及边界条件。使用两个指针p和q，一个指针先走k-1步，然后第二个指针开始走。当第一个指针指向单链表的最后一个节点时，第二个指针指向倒数第k个节点。代码如下：

1 /* 2 public class ListNode { 3     int val; 4     ListNode next = null; 5   6     ListNode(int val) { 7         this.val = val; 8     } 9 }*/10 public class Solution {11     public ListNode FindKthToTail(ListNode head,int k) {12         if(head==null||k==0){13             return null ;14         }15         ListNode p = new ListNode(0) ;16         ListNode q = new ListNode(0) ;17         p = head ;18         q = head ;19         while(k>1&&p.next!=null){20             p=p.next ;21             k-- ;22         }23         if(k>=2){24             return null ;25         }26         while(p.next !=null&&q.next!=null){27             p=p.next ;28             q=q.next;29         }30         return q ; 31     }32 }