题目
给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号,请查找并返回倒数第 cnt 个训练项目编号。
示例 1:
输入:head = [2,4,7,8], cnt = 1
输出:8
提示:
1 <= head.length <= 100
0 <= head[i] <= 100
1 <= cnt <= head.length
思路
先判断头节点是否是空
if(head == null){
return null;
}
再定义快慢指针指向头节点
ListNode fast = head, slow = head;
再用for循环让fast快指针先走K步
同样判断快指针是否走到头
for(int i = 0; i < k; i++){
if(fast == null){
return null;
}
fast = fast.next;
}
再让慢指针和快指针一起走到目标值位置
while(fast != null){
fast = fast.next;
slow = slow.next;
}
代码
/**
- Definition for singly-linked list.
- public class ListNode {
-
int val;
-
ListNode next;
-
ListNode() {}
-
ListNode(int val) { this.val = val; }
-
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
- }
*/
class Solution {
public ListNode trainingPlan(ListNode head, int cnt) {
if(head null){
return null;
}
ListNode fast = head, slow = head;
for(int i=0; i<cnt; i++){
if(fastnull){
return null;
}
fast = fast.next;
}
while(fast!=null){
fast =fast.next;
slow = slow.next;
}
return slow;
}
}
时间复杂度:O(n)
空间复杂度:O(1)