【408DS算法题】022基础-递增输出单链表中的结点值

Index

• • 题目
  • 分析实现
  • • 总结
• 以上内容稍后补全，以下内容来自https://blog.csdn.net/weixin_60702024/article/details/141336041
• • 题目
  • 分析实现
  • 总结分析

题目

给定单链表的头结点，按照递增的顺序，输出单链表结点的值。

分析实现

具体实现如下：

总结

注意delete执行后，只会将指针指向的内容删除，但指针变量依旧存在。

以上内容稍后补全，以下内容来自https://blog.csdn.net/weixin_60702024/article/details/141336041

Index

• • 题目
  • 分析实现
  • • 总结
• 以上内容稍后补全，以下内容来自https://blog.csdn.net/weixin_60702024/article/details/141336041
• • 题目
  • 分析实现
  • 总结分析

题目

试编写在带头结点的单链表L中删除一个最小值结点的高效算法。

分析实现

在思路上本题类似于【查找链表的倒数第k个节点】，通过记录目标结点的前驱结点来达到删除目标结点的目的。额外地，本题还新增了一对指针minV和minPre来特别记录真正的目标结点。

具体实现如下 ：

void deleteMin(LNode* head){
	// cur-当前待判断结点	pre- cur的前驱结点，用于存储候选minPre
	LNode *cur = head->next, *pre = head;
	// minV-结点元素最小的结点	 minPre- minV的前驱结点，用于删除minV
	LNode *minV = cur, *minPre = pre;
	while(cur){
		if(cur->val < minV->val){
			// 维护 minV 和 minPre
			minV = cur;
			minPre = pre;
		}
		pre = cur;
		cur = cur->next;
	}
	minPre->next = minV->next;
	delete minV;
}

总结分析

本体思路依旧不难想出，变量的含义也十分明确。重点在于通过本题练习写出代码的过程中保持代码的简洁，同时又不缺少必要的变量。