剑指Offer:链表中倒数第k个节点

题目

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

分析

获得给定链表的倒数第k个字节,最直接的做法是先遍历整个链表获取链表节点的个数。假设链表有n个节点,那么倒数第k个节点就是从开头数的第n-k+1个节点。也就是说我们需要遍历链表两次,第一次统计链表节点的个数,第二次就能找到倒数第k个节点了。

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
/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode list,int k) {
if (list == null) return list;

ListNode node = list;
int count = 0;
while (node != null) {
count++;
node = node.next;
}
if (count < k) return null;

ListNode p = list;
for (int i = 0; i < count - k; i++) {
p = p.next;
}
return p;
}
}

但以上的方法并不是最优的解决办法,我们可以只遍历一遍链表就能找到倒数第k个节点。

我们可以定义两个指针,第一个指针从链表的头部开始遍历走到第k-1个节点,第二个指针先“按兵不动”。从第k步开始,第二个指针也开始从头遍历链表。两个指针之间始终保持k-1的距离,当第一个指针走到尾节点时,第二个指针正好走到倒数第k个节点。

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
/*
public class ListNode {
int val;
ListNode next = null;

ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head,int k) {
if (head == null || k <= 0)
return null;
ListNode first = head;
ListNode second = head;
for (int i = 0; i < k-1; i ++) {
if (first == null)
return null;
first = first.next;
}
if (first == null) return null;
while (first.next!=null) {
first = first.next;
second = second.next;
}
return second;
}
}

对于以上方法需要注意以下几点:

  • 判断给定的头结点是否为空(防止程序崩溃)
  • 判断链表的节点个数是否小于k
有收获再赞赏哦🤭
------ 本文结束感谢您的阅读-------------
0%