设计一个算法,求一个非空循环单链表l中最后一个最大节点的逻辑序号。
时间: 2023-04-20 07:00:21 浏览: 140
算法如下:
1. 定义一个变量max记录当前最大值,初始值为第一个节点的值,定义一个变量pos记录最大节点的位置,初始值为1。
2. 从第二个节点开始遍历循环单链表,如果当前节点的值大于max,则更新max和pos的值。
3. 遍历到链表尾部后,如果最后一个节点的值大于等于max,则返回pos,否则返回1。
4. 如果循环单链表为空,则返回。
代码实现如下:
int findLastMaxPos(Node *l) {
if (l == NULL) return ;
int max = l->data;
int pos = 1;
Node *p = l->next;
int i = 2;
while (p != l) {
if (p->data > max) {
max = p->data;
pos = i;
}
p = p->next;
i++;
}
if (l->data >= max) return pos;
else return 1;
}
相关问题
设计一个算法,查找带头节点的非空单链表l中第一个最大节点(最大节点可能有多个),并返回该节点的逻辑序号。
算法如下:
1. 定义一个变量max记录当前最大值,初始值为l的头节点的值,定义一个变量index记录当前最大值的逻辑序号,初始值为1。
2. 从l的第二个节点开始遍历整个链表,如果当前节点的值大于max,则更新max为当前节点的值,更新index为当前节点的逻辑序号。
3. 遍历完整个链表后,返回index即可。
代码实现如下:
int findMaxNode(ListNode* l) {
int max = l->val;
int index = 1;
ListNode* p = l->next;
while (p != NULL) {
if (p->val > max) {
max = p->val;
index = index + 1;
}
p = p->next;
}
return index;
}
设计一个算法,查找带头结点的非空单链表L中的一个最后一个最小结点,并返回该结点的逻辑序号
可以使用双指针法来解决这个问题。定义两个指针p和q,初始时p和q都指向头结点。然后,让p指针先走k步,然后p和q指针同时向后移动,直到p指针到达链表的末尾。此时,q指针所指向的结点就是最后一个最小结点。
具体实现如下:
1. 定义两个指针p和q,初始时都指向头结点。
2. 让p指针先走k步,k为链表的长度。
3. 然后p和q指针同时向后移动,直到p指针到达链表的末尾。
4. 返回q指针所指向的结点的逻辑序号。
代码实现如下:
int findLastMinNode(ListNode* head) {
ListNode* p = head;
ListNode* q = head;
int k = ;
while (p != NULL) {
k++;
p = p->next;
}
p = head;
for (int i = ; i < k; i++) {
p = p->next;
}
while (p != NULL) {
p = p->next;
q = q->next;
}
return q->val;
}