1 问题
找出单链表的倒数第K个元素，例如给定链表 1--2---3--4--5--6---7 ，则单链表的倒数第K=3个元素为5.
2 思路分析
方法一： 顺序遍历两遍法
1）首先遍历一遍链表，计算出链表中的节点数n.
2)把倒数第k个数，转成正数第n-k个元素。
3）遍历链表，找到第n-k个元素。
方法二：快慢指针法
1）因为单链表只能从头到尾遍历元素，因此可以定义两个快慢指针
2）快指针比慢指针先移动K步，然后一起移动，
3）快指针到链表尾部时，慢指针就正好指向倒数第K个元素
3 代码实现
package linkedlist.LookLnode;public class LookLnode {public static void main(String[] args) {LNode head = ConstrucList();LNode result=null;System.out.print("链表：");Print(head);result=findLastLnode(head,3);if (result!=null){System.out.printf("\n链表的倒数三个元素为%d",result.date);}}//首先定义一个单链表public static LNode ConstrucList(){int i=0;LNode head=new LNode();head.next=null;LNode temp=null;LNode cur=head;//构建一个链表for (;i<8;i++){temp=new LNode();temp.date=i;temp.next=null;cur.next=temp;cur=temp;}return head;}//打印单链表的数据public static void Print(LNode head){for (LNode cur=head.next;cur!=null;cur=cur.next){System.out.print(cur.date+" ");}}/*** 找出链表的倒数第K个节点* @param head 头结点* @return 倒数第K个节点*/public static LNode findLastLnode(LNode head,int k){if (head==null|| head.next==null){return head;}LNode fast=null;//快指针LNode slow=null;//慢指针fast=slow=head.next;int i=0;for (;i<k && fast!=null;++i){//前移K步fast=fast.next;}//判断k是否大于链表的长度if (i<k){return null;}while (fast!=null){slow=slow.next;fast=fast.next;}return slow;}}
class LNode{LNode next;int date;
}