当前位置: 首页 > >

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

发布时间:

package com.itcast.demo.ListNode;


import java.util.Scanner;

public class ListNodeDemo {

public static void main(String[] args) {
ListNodeDemo knode = new ListNodeDemo();
System.out.println("请随意输入一串数字:");
Scanner sc = new Scanner(System.in);
String[] a = sc.nextLine().split(" ");// 构造数据源
System.out.println("请随意输入K的值:");
int k = sc.nextInt(); // k的范围[0,a.length-1] ,此处略去了审查
knode.printResult(knode, a, k);
}

// 打印结果
private void printResult(ListNodeDemo knode, E[] e, int k) {
// 1)创建一个除头节点外有num个节点的单链表,
int length = e.length;
Node first = knode.createList(e);
Node q = knode.KNode(first, k); // 2)找到倒数第k个节点
System.out.println("这是单链表:");
for (int i = 0; i < length - 1; i++) {
System.out.print(first.next.data + "-->");
first = first.next;
}
System.out.print(first.next.data);
System.out.println("
这是单链表的倒数第" + k + "个元素:" + q.data);
}

// 输出该链表中倒数第k个结点
private Node KNode(Node first, int k) {
int n = -1; // n保存节点的个数,从正向计数,节点下标为[0,n],即总共有n+1个真正节点
Node r = first;
while (r.next != null) { // 创建一个循环单链表,尾指针指向first.next
r = r.next;
n++;
}
Node q = first;// q指向倒数第k个节点,倒数第k个节点即为正数第n-k个节点
int t = n - k;
while (t >= 0) {
q = q.next;
t--;
}
return q;
}

// 创建带头节点的无环单链表,真正的节点有m个
public Node createList(E[] keys) {
Node first = new Node(null, null); // 头节点
Node r = first; // 指向链表的尾节点
for (E e : keys) { // 产生0~100之间数字
Node node = new Node(e, null);
r.next = node;
r = node;
}
r.next = null; // 若是构建无环单链表,此处 r.next = null;
return first;
}
}

class Node {
public E data;
public Node next;

public Node(E data, Node next) {
super();
this.data = data;
this.next = next;
}
}





结果:


请随意输入一串数字:
1 2 6 85 98 74 4 5?
请随意输入K的值:
5
这是单链表:
1-->2-->6-->85-->98-->74-->4-->5
这是单链表的倒数第5个元素:6





友情链接: