1 package Solution;
2
3 public class No15FindKthNodeFromEnd {
4
5 public static class ListNode {
6 int data;
7 ListNode next;
8
9 public ListNode(int value, ListNode next) {
10 this.data = value;
11 this.next = next;
12 }
13 }
14
15 public static ListNode findKthNodeFromEnd(ListNode head, int k) {
16 if (head == null)
17 throw new RuntimeException("待查找的链表不能为空");
18 if (k <= 0)
19 throw new RuntimeException("输入的位置数字不合法");
20 ListNode ahead = head;
21 ListNode behind = head;
22 // 第一个指针先指向K-1,并检验链表中节点个数是否大于k
23 int count = 1;
24 for (int i = 0; i < k - 1; i++) {
25 if (ahead.next != null) {
26 ahead = ahead.next;
27 count++;
28 } else
29 throw new RuntimeException("链表节点个数:" + count + " 小于输入K的个数:" + k);
30 }
31 while (ahead.next != null) {
32 ahead = ahead.next;
33 behind = behind.next;
34 }
35 return behind;
36 }
37
38 public static void main(String[] args) {
39 ListNode node1 = new ListNode(4, null);
40 ListNode node2 = new ListNode(3, node1);
41 ListNode node3 = new ListNode(2, node2);
42 ListNode head = new ListNode(1, node3);
43 ListNode find = findKthNodeFromEnd(head, 3);
44 System.out.println("找到的节点位" + find.data);
45 ListNode find2 = findKthNodeFromEnd(head, 5);
46 System.out.println("找到的节点位" + find2.data);
47 }
48 }