【剑指offer】-链表中倒数第K个结点-14/67

1. 题目描述

输入一个链表,输出该链表中倒数第k个结点
假设题目为: 3 【1,2,3,4,5,6】

2. 题目思路

2.1 第一种思路:两个结点分别跑

1 判断当前给的链表head是不是null,如果是的话,返回null
2. 判断k的值,如果k的值,小于等于0,返回null
3. 建立两个结点,指向head(注意:这里一定要明白当前链表是不是有头结点的,该题不含有头结点)
链表
4. 先让p1结点跑k-1(2)次(要时刻注意,p1.next是否走到了null)在这里插入图片描述
5. 然后p1和p2同时开始跑,等到p1.next跑到null时,p2所指的指针就是倒数第K(3)个结点在这里插入图片描述

2.2 第二种思路:一个结点跑

1 判断当前给的链表head是不是null,如果是的话,返回null
2. 判断k的值,如果k的值,小于等于0,返回null
3. 建立一个结点,遍历一遍链表,找到链表的长度len在这里插入图片描述
4. 重新定义结点p1,此时,num = (len - k + 1)就是链表在结点中的位置,位置必须大于0
5. 此时链表p1指向第一个数值。所以,只需要跑num - 1次,即可找到倒数第K个数

3. 题目代码

3.1 第一种思路:两个结点分别跑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public ListNode FindKthToTail(ListNode head,int k) {
if(head == null || k <= 0){
return null;
}
ListNode p1 = head;
ListNode p2 = head;
for(int i = 0; i < k - 1; i++){
if(p1.next == null){
return null;
}else{
p1 = p1.next;
}
}
while(p1.next != null){
p1 = p1.next;
p2 = p2.next;
}
return p2;
}

3.2 第二种思路:一个结点跑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode FindKthToTail(ListNode head, int k) {
if (head == null || k <= 0) {
return null;
}
ListNode p1 = head;
int len = 0;
while (p1 != null) {
p1 = p1.next;
len++;
}
int num = len - k + 1;
p1 = head;
if (num <= 0) {
return null;
}
for (int i = 1; i < num; i++) {
p1 = p1.next;
}
return p1;
}
打赏
  • 版权声明: 本博客所有文章除特别声明外,均采用 Apache License 2.0 许可协议。转载请注明出处!
  • © 2017-2020 苦酒
  • PV: UV:

请我喝杯咖啡吧~

支付宝
微信