首页 > 代码库 > 13输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
13输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
转载请注明出处：http://www.cnblogs.com/wuzetiandaren/p/4250795.html
声明：现大部分文章为寻找问题时在网上相互转载，此博是为自己做个记录记录，方便自己也方便有类似问题的朋友，本文的思想也许有所借鉴，但源码均为本人实现，如有侵权，请发邮件表明文章和原出处地址，我一定在文章中注明。谢谢。
题目：输入一个单向链表，输出该链表中倒数第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<E> { 3 public E data; 4 public Node next; 5 public Node(E data, Node next) { 6 super(); 7 this.data =http://www.mamicode.com/ 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 <E> 8 * 9 */10 public class _13KListNode<E> {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<length-1;i++){30 System.out.print(first.next.data+"-->");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<E> {71 public E data;72 public Node next;73 public Node(E data, Node next) {74 super();75 this.data =http://www.mamicode.com/ data;76 this.next = next;77 }78 }
运行结果：
这是单链表：
23-->56-->11-->88-->67-->46-->20-->42-->17-->98-->58-->33-->19
这是单链表的倒数第5个元素：42
13输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。