寻找模结点
[!Tip]
本节源代码见Github链接🔗
问题描述
给定一个单向链表，链表的结点编号i为1,2,3,...,n，其中n为链表中元素的个数，编写一个函数从表头开始找到最后一个满足i%k=0条件的元素，k是一个整数常量。例如，如果n为19，k为3，那么应该返回第18个结点
核心思路
由于n的值是未知的，所以需要一直遍历，直到遍历完链表。并在遍历过程中保存下最后一个模结点。
实现代码
【👉🏻>>点击展开查看代码】
/**
* 寻找最后一个模结点
*
* @param headNode
* @return NormalListNode
* @author: Max Solider
* @date: 2022/10/9 14:18
*/
static NormalListNode getLastModularNode(NormalListNode headNode, int k) {
if (headNode == null) {
return headNode;
}
NormalListNode modularNode = null;
int i = 1;
while (headNode != null) {
if (i % k == 0 ) {
modularNode = headNode;
}
headNode = headNode.getNext();
i++;
}
return modularNode;
}
时间复杂度
时间复杂度为O(n)，用于遍历链表。
空间复杂度
空间复杂度为O(1)，用于存储临时变量。