forked from Wang-Jun-Chao/coding-interviews
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathTest15.java
More file actions
92 lines (74 loc) · 2.69 KB
/
Copy pathTest15.java
File metadata and controls
92 lines (74 loc) · 2.69 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/**
* Author: 王俊超
* Date: 2015-04-23
* Time: 16:20
* Declaration: All Rights Reserved !!!
*/
public class Test15 {
public static class ListNode {
int value;
ListNode next;
}
/**
* 输入一个键表，输出该链表中倒数第k 个结点．为了符合大多数人的习惯，
* 本题从1开始计数，即链表的尾结点是倒数第1个结点．例如一个链表有6个结点，
* 从头结点开始它们的值依次是1、2、3、4、5 6。这个链表的倒数第3个结点是值为4的结点．
*
* @param head 链表的头结点
* @param k 倒数第k个结点
* @return 倒数第k个结点
*/
public static ListNode findKthToTail(ListNode head, int k) {
// 输入的链表不能为空，并且k大于0
if (k < 1 || head == null) {
return null;
}
// 指向头结点
ListNode pointer = head;
// 倒数第k个结点与倒数第一个结点相隔k-1个位置
// pointer先走k-1个位置
for (int i = 1; i < k; i++) {
// 说明还有结点
if (pointer.next != null) {
pointer = pointer.next;
}
// 已经没有节点了，但是i还没有到达k-1说明k太大，链表中没有那么多的元素
else {
// 返回结果
return null;
}
}
// pointer还没有走到链表的末尾，那么pointer和head一起走，
// 当pointer走到最后一个结点即，pointer.next=null时，head就是倒数第k个结点
while (pointer.next != null) {
head = head.next;
pointer = pointer.next;
}
// 返回结果
return head;
}
public static void main(String[] args) {
ListNode head = new ListNode();
head.value = 1;
head.next = new ListNode();
head.next.value = 2;
head.next.next = new ListNode();
head.next.next.value = 3;
head.next.next.next = new ListNode();
head.next.next.next.value = 4;
head.next.next.next.next = new ListNode();
head.next.next.next.next.value = 5;
head.next.next.next.next.next = new ListNode();
head.next.next.next.next.next.value = 6;
head.next.next.next.next.next.next = new ListNode();
head.next.next.next.next.next.next.value = 7;
head.next.next.next.next.next.next.next = new ListNode();
head.next.next.next.next.next.next.next.value = 8;
head.next.next.next.next.next.next.next.next = new ListNode();
head.next.next.next.next.next.next.next.next.value = 9;
System.out.println(findKthToTail(head, 1).value); // 倒数第一个
System.out.println(findKthToTail(head, 5).value); // 中间的一个
System.out.println(findKthToTail(head, 9).value); // 倒数最后一个就是顺数第一个
System.out.println(findKthToTail(head, 10));
}
}