题目描述:

输入一个链表,输出该链表中倒数第k个结点。

链表结构如下:

1
2
3
4
5
6
7
8
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}

由链表结构就能知道由此基础建立的链表不能直接知道该链表的长度,需要通过node = node.next 一步一步遍历链表才能获取链表长度。

因此最先想到的方法就是先遍历一遍链表,获取链表长度,然后通过链表长度和k数值的差得出目标地址。实现方法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode newHead = head, pre = head;
int count = 0; // 获取链表长度
while(pre != null){
count++;
pre = pre.next;
}
if(count < k) // 不存在倒数第k个链表
return null;
else{
int num = count - k; // num为正数的目的地址,与倒数第k个链表值一致
while(num > 0){
newHead = newHead.next;
num--;
}
return newHead;
}
}
}

有了基础思路,下一步就是简化代码,用更简洁的表达将效果呈现出来。以下使用for循环:

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) { //5,{1,2,3,4,5}
ListNode p, q;
p = q = head;
int i = 0;
for (; p != null; i++) {
if (i >= k)
q = q.next;
p = p.next; // p相当于上面的pre链表,用于测量链表长度
}
return i <= k ? null : q;
}
}

也可以使用while一次遍历

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
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
ListNode pre=null,p=null;
//两个指针都指向头结点
p=head;
pre=head;
//记录k值
int a=k;
//记录节点的个数
int count=0;
//p指针先跑,并且记录节点数,当p指针跑了k-1个节点后,pre指针开始跑,
//当p指针跑到最后时,pre所指指针就是倒数第k个节点
while(p!=null){
p=p.next;
count++;
if(k<1){
pre=pre.next;
}
k--;
}
//如果节点个数小于所求的倒数第k个节点,则返回空
if(count<a) return null;
return pre;

}
}

其实思路是一致的,就是通过得到链表长度,再得到n-k位置的链表值。