LeetCode题解-链表标签:返回倒数第k个节点


题目:实现一种算法,找出单向链表中倒数第k个节点。返回该节点的值。

Leetcode在线OJ系统:传送门

示例:

graph LR
A[1]-->B[2]
B[2]-->C[3]
C[3]-->D[4]
D[4]-->E[5]
1
2
输入:k = 2
输出:4

说明:给定的 k 保证是有效的。

思路:双指针法。定义两个指针firstsecondfirst指针先走k - 1步,然后second指针和first指针同时走,每次走一步,当first指针到达链表末尾时,second指针指向的节点即为倒数第k个节点。

Java语言实现如下:

单链表节点类定义可查看文章:数据结构之链表-基础知识

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public static int kthToLast(SinglyLinkedListNode head, int k) {
if (head == null || k <= 0) {
return 0;
}
SinglyLinkedListNode first = head;
SinglyLinkedListNode second = head;
while (k-- > 1) {
// 长度不足k
if (first.next == null) {
return 0;
}
first = first.next;
}
while (first.next != null) {
first = first.next;
second = second.next;
}
return second.val
}
作者

SunChaser

发布于

2020-12-23

更新于

2020-12-23

许可协议

评论