题目描述请编写程序将nnn个整数顺次插入一个初始为空的单链表的表头。对任一给定的整数xxx查找其是否在链表中。输入格式输入首先在第一行给出非负整数nnn≤20\le 20≤20随后一行给出nnn个 int 范围内的整数数字间以空格分隔。最后一行给出待查找的xxx为 int 范围内的整数。输出格式如果找到了xxx所在的位置则输出该位置上链表结点的数据否则在一行中输出x 未找到。其中x是输入的xxx的值。输入样例5 1 2 3 4 5 4输出样例4输入样例5 1 2 3 4 5 0输出样例0 未找到。解题思路本题考察单链表的建立与按值查找操作。题目要求将nnn个整数顺次插入表头即使用头插法建表每读入一个整数就new一个结点并插到当前链表头部因此建表完成后链表中的结点顺序为输入序列的逆序。按值查找只需从表头开始沿next指针逐个访问结点将每个结点的data与目标值xxx比较一旦相等即查找成功输出该结点的数据若遍历完整条链表都没有找到说明xxx不在链表中按要求输出x 未找到。。时间复杂度建立链表为O(n)O(n)O(n)按值查找最坏需要遍历全部nnn个结点为O(n)O(n)O(n)总体O(n)O(n)O(n)。空间复杂度链表结点数为nnn为O(n)O(n)O(n)。代码流程说明定义Node结构体包含数据域data、指针域next构造函数将next初始化为nullptr。main函数中先读入整数个数n将链表头指针head初始化为空。循环n次每次读入一个整数vnew出新结点p头插法插入链表p-next head; head p;。读入待查找的目标值x。指针p指向表头用while (p)遍历链表若p-data x说明找到输出x并结束程序否则p p-next继续向后。循环正常结束说明链表遍历完毕仍未找到输出x 未找到。。代码实现#includeiostreamusingnamespacestd;structNode{intdata;Node*next;Node(intd):data(d),next(nullptr){}};intmain(){intn,x;cinn;Node*headnullptr;for(intk0;kn;k){intv;cinv;Node*pnewNode(v);p-nexthead;headp;}cinx;Node*phead;while(p){if(p-datax){coutxendl;return0;}pp-next;}coutx 未找到。endl;return0;}代码流程图是否否是是否开始读入 n初始化 head 为空是否还有 k n 个数未读入读入 v创建新结点 pp-next headhead p读入待查找的 xp 指向表头p 是否非空输出 x 未找到结束p-data 是否等于 x输出 xp p-next解题流程图是否是否读入 n 个整数头插法依次建立单链表读入待查找的 x从表头开始遍历链表当前结点的 data 是否等于 x输出 x, 查找成功是否还有后继结点移动到下一个结点输出 x 未找到, 查找失败结束