转载请注明出处： 

声明：现大部分文章为寻找问题时在网上相互转载，此博是为自己做个记录记录，方便自己也方便有类似问题的朋友，本文的思想也许有所借鉴，但源码均为本人实现，如有侵权，请发邮件表明文章和原出处地址，我一定在文章中注明。谢谢。

题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。

题目分析：

　　1.链表的倒数第0个结点为链表的尾指针，设为r，则r指向最后一个节点，r.next=null。

　　2.创建一个带头节点的单链表，first指向头节点。

　　3.单链表的长度假设为N, n=N-1，则正向单链表的下标为[0,n]，倒数第k个节点实际上是正数第n-k个节点。

　　4.开始只知道单链表的头指针，因此需要遍历两次单链表：第一次求出单链表的长度，并找到尾节点；第二次找到正数第n-k个节点(即为倒数第k个节点)。

　　

节点的数据结构：

1 //创建一个泛型节点类 2 class Node
     
       { 3     public E data; 4     public Node next; 5     public Node(E data, Node next) { 6         super(); 7         this.data = data; 8         this.next = next; 9     }10 }
     

注意：这个节点的市局类型是泛型的，以后可以传入任何类型的数据以保证代码的通用性，此处实现的时候，传入的是Integer类型的数据。

java具体实现：

 

1 package com.interview; 2  3 import java.util.Random; 4 /** 5  * 题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。 6  * @author wjh 7  * @param 
      
        8  * 9  */10 public class _13KListNode
       
         {11 12     /**13      * @param args14      */15     public static void main(String[] args) {16         _13KListNode knode = new _13KListNode();17         Integer[] a = {23,56,11,88,67,46,20,42,17,98,58,33,19};//构造数据源18         int k = 5;  //k的范围[0,a.length-1] ,此处略去了审查19         knode.printResult(knode,a,k);20     }21 22     //打印结果 23     private void printResult(_13KListNode knode,E[] e,int k){        24         //1)创建一个除头节点外有num个节点的单链表,25         int length = e.length;        26         Node first = knode.createList(e);  27         Node q = knode.KNode(first, k);   //2)找到倒数第k个节点28         System.out.println("这是单链表：");29         for(int i=0;i
        
         ");31             first =first.next;32         }33         System.out.print(first.next.data);34         System.out.println("\n这是单链表的倒数第"+k+"个元素："+q.data);35     }36     37     //输出该链表中倒数第k个结点38     private Node  KNode(Node first, int k){39         int n = -1;   //n保存节点的个数,从正向计数，节点下标为[0,n],即总共有n+1个真正节点40         Node r = first;41         while(r.next!=null){  //创建一个循环单链表,尾指针指向first.next42             r = r.next;43             n++;44         }45         Node q = first;//q指向倒数第k个节点,倒数第k个节点即为正数第n-k个节点46         int t=n-k;47         while(t>=0){48             q = q.next;49             t--;50         }51         return q;52     }53     54     //创建带头节点的无环单链表,真正的节点有m个55     public Node createList(E[] keys){56         Node first = new Node(null,null);    //头节点57         Node r = first;   //指向链表的尾节点58         Random rand = new Random();59         for(E e: keys){  //产生0~100之间数字60             Node node = new Node(e,null);61             r.next = node;62             r = node;63         }64         r.next = null;       //若是构建无环单链表，此处   r.next = null;65         return first;66     }    67 }68 69 //创建一个泛型节点类70 class Node
         
           {71     public E data;72     public Node next;73     public Node(E data, Node next) {74         super();75         this.data = data;76         this.next = next;77     }78 }
         
        
       
      

 

运行结果：

这是单链表：

23-->56-->11-->88-->67-->46-->20-->42-->17-->98-->58-->33-->19

这是单链表的倒数第5个元素：42