程序员经验分享-hwhale

笔试面试常考数据结构-单链表常用操作编程实现

2023-11-20

单链表是笔试以及面试手写代码中常考的数据结构之一。下面实现了单链表的常见操作：创建单链表、删除节点、打印单链表（包括正向打印以及逆向打印）、反转单链表、找出单链表的倒数第K个节点、合并两个有序单链表等操作。


代码（C++）：

  1. //笔试面试单链表常用操作编程实现  
  2. #include <iostream>  
  3. #include <stack>  
  4. #include <cstdlib>  
  5.   
  6. using namespace std;  
  7.   
  8. //单链表节点数据结构定义  
  9. typedef struct link_node_s{  
  10.     int m_val;  
  11.     struct link_node_s *next;  
  12. }link_node_t,*link_list_t;  
  13.   
  14. //函数:创建单链表(头插法)  
  15. link_list_t create_linklist(int *a,int n);  
  16.   
  17. //函数:打印单链表(从头到尾)  
  18. void print_linklist(link_list_t head);  
  19.   
  20. //函数:打印单链表(从尾到头)  
  21. void print_linklist_reverse(link_list_t head);  
  22.   
  23. //函数:新建链表节点  
  24. link_list_t creart_linknode(int val);  
  25.   
  26. //函数:删除链表中的某一个节点(前提条件:该节点一定存在)  
  27. //性能要求:在O(1)时间复杂度内实现  
  28. void delete_node_exist(link_list_t *head,link_list_t node_deleted);  
  29.   
  30. //函数:删除链表中数据值等于给定值的节点  
  31. void delete_node(link_list_t *head,int val);  
  32.   
  33. //函数:获得链表中的倒数第K个节点  
  34. link_list_t get_kth_node(link_list_t head,int k);  
  35.   
  36. //函数:反转链表  
  37. link_list_t reverse_linklist(link_list_t head);  
  38.   
  39. //函数:合并两个已排序的链表(递归方法实现)  
  40. link_list_t merge_linklist_recursive(link_list_t head1,link_list_t head2);  
  41.   
  42. int main(){  
  43.     const int num1 = 8;  
  44.     const int num2 = 10;  
  45.     int *a = new int[num1];  
  46.     int *b = new int[num2];  
  47.     int *a_sorted = new int[num1];  
  48.     int *b_sorted = new int[num2];  
  49.   
  50.     srand(1);  
  51.     for(int i = 0;i < num1;++i){  
  52.         *(a + i) = rand() % 100;  
  53.         *(a_sorted + i) = 50 - i * 2 + 8;  
  54.     }  
  55.       
  56.     for(int i = 0;i < num2;++i){  
  57.         *(b + i) = rand() % 200;  
  58.         *(b_sorted + i) = 50 - i * 4 + 1;  
  59.     }  
  60.   
  61.     cout << "**********创建链表测试**********" << endl;  
  62.     link_list_t list1 = create_linklist(a,num1);  
  63.     link_list_t list2 = create_linklist(b,num2);  
  64.     link_list_t list_sorted1 = create_linklist(a_sorted,num1);  
  65.     link_list_t list_sorted2 = create_linklist(b_sorted,num2);  
  66.   
  67.     cout << "**********输出链表测试(正向输出)**********" << endl;  
  68.     cout << "链表1:" << endl;  
  69.     print_linklist(list1);  
  70.     cout << "链表1(已序):" << endl;  
  71.     print_linklist(list_sorted1);  
  72.     cout << "链表2(已序):" << endl;  
  73.     print_linklist(list_sorted2);  
  74.   
  75.     cout << "**********输出链表测试(逆向输出)**********" << endl;  
  76.     print_linklist_reverse(list1);  
  77.   
  78.   
  79.     cout << "**********获取链表的倒数第K个节点测试**********" << endl;  
  80.     int k = 3;  
  81.     link_list_t kth_node = get_kth_node(list1,k);  
  82.     if(NULL == kth_node)  
  83.         cout << "链表中倒数第" << k << "个节点不存在" << endl;  
  84.     else  
  85.         cout << "链表中倒数第" << k <<"个节点是: " <<kth_node->m_val << endl;   
  86.   
  87.     k = 8;  
  88.     kth_node = get_kth_node(list1,k);  
  89.     if(NULL == kth_node)  
  90.         cout << "链表中倒数第" << k << "个节点不存在" << endl;  
  91.     else  
  92.         cout << "链表中倒数第" << k <<"个节点是: " <<kth_node->m_val << endl;   
  93.   
  94.     k = 11;  
  95.     kth_node = get_kth_node(list1,k);  
  96.     if(NULL == kth_node)  
  97.         cout << "链表中倒数第" << k << "个节点不存在" << endl;  
  98.     else  
  99.         cout << "链表中倒数第" << k <<"个节点是: " <<kth_node->m_val << endl;   
  100.   
  101.     cout << "**********删除链表中一定存在的节点测试(输入参数是要删除的节点指针)**********" << endl;  
  102.     link_list_t node_deleted = list1;  
  103.     while(node_deleted->m_val != *(a + 4))  
  104.         node_deleted = node_deleted->next;  
  105.   
  106.     cout << "删除节点" << *(a + 4) << "之后的单链表:" << endl;  
  107.     delete_node_exist(&list1,node_deleted);  
  108.     print_linklist(list1);  
  109.       
  110.     node_deleted = list1;  
  111.     while(node_deleted->m_val != *(a + 6))  
  112.         node_deleted = node_deleted->next;  
  113.   
  114.     cout << "删除节点" << *(a + 6) << "之后的单链表:" << endl;  
  115.     delete_node_exist(&list1,node_deleted);  
  116.     print_linklist(list1);  
  117.   
  118.     cout << "**********删除链表中值等于给定值的节点测试(不一定存在,输入参数是int型值)**********" << endl;  
  119.     const int val_deleted = 22;  
  120.     delete_node(&list1,val_deleted);  
  121.     cout << "删除值等于" << val_deleted << "之后的链表:" << endl;  
  122.     print_linklist(list1);  
  123.   
  124.     cout << "**********合并链表测试**********" << endl;  
  125.     link_list_t merge_list_head = merge_linklist_recursive(list_sorted1,list_sorted2);  
  126.     print_linklist(merge_list_head);  
  127.   
  128.       
  129.     cout << "**********逆转链表测试**********" << endl;  
  130.     link_list_t head_reverse = reverse_linklist(<span style="font-family: Arial, Helvetica, sans-serif;">merge_list_head</span><span style="font-family: Arial, Helvetica, sans-serif;">);</span>  
  131.     cout << "逆转之后的链表:" << endl;  
  132.     cout << "头节点:" << head_reverse->m_val << endl;  
  133.     print_linklist(head_reverse);  
  134.       
  135.     return 0;  
  136. }  
  137.   
  138. //函数:创建单链表(头插法)  
  139. link_list_t create_linklist(int *a,int n){  
  140.     link_list_t head = NULL;  
  141.   
  142.     if(NULL == a || 0 == n)  
  143.         return NULL;  
  144.   
  145.     for(int i = 0;i < n;++i){  
  146.         link_list_t new_node = creart_linknode(*(a + i));  
  147.   
  148.         if(NULL == head){  
  149.             head = new_node;  
  150.         }  
  151.         else{  
  152.             new_node->next = head;  
  153.             head = new_node;  
  154.         }  
  155.     }  
  156.   
  157.     return head;  
  158. }  
  159.   
  160. //函数:新建链表节点  
  161. link_list_t creart_linknode(int val){  
  162.     link_list_t node = new link_node_t;  
  163.     node->m_val = val;  
  164.     node->next = NULL;  
  165.   
  166.     return node;  
  167. }  
  168.   
  169. //函数:打印单链表  
  170. void print_linklist(link_list_t head){  
  171.     link_list_t node = head;  
  172.   
  173.     cout << "正向输出单链表" << endl;  
  174.     while(node != NULL){  
  175.         cout << node->m_val << " ";  
  176.         node = node->next;  
  177.     }  
  178.     cout << endl;  
  179.   
  180.     return;  
  181. }  
  182.   
  183. //函数:打印单链表(从尾到头)  
  184. void print_linklist_reverse(link_list_t head){  
  185.     stack<int> node_stack;  
  186.     link_list_t node = head;  
  187.     while(node != NULL){  
  188.         node_stack.push(node->m_val);  
  189.         node = node->next;  
  190.     }  
  191.   
  192.     cout << "逆向输出单链表" << endl;  
  193.     while(!node_stack.empty()){  
  194.         cout << node_stack.top() << " ";  
  195.         node_stack.pop();  
  196.     }  
  197.     cout << endl;  
  198.   
  199.     return;  
  200. }  
  201.   
  202.   
  203. //函数:删除链表中的某一个节点(前提条件:该节点一定存在)  
  204. //性能要求:在O(1)时间复杂度内实现  
  205. void delete_node_exist(link_list_t *head,link_list_t node_deleted){  
  206.     //算法思想:  
  207.     //通过拷贝要删除节点的后继节点的内容覆盖要删除节点的内容,然后删除要删除节点的后继节点即可  
  208.     //要考虑的特殊情况是:要删除的节点是链表尾部节点,仍然需要遍历链表  
  209.     if(NULL == head || NULL == node_deleted)  
  210.         return;  
  211.   
  212.     //要删除的节点不是尾节点  
  213.     if(node_deleted->next != NULL){  
  214.         link_list_t next_node = node_deleted->next;  
  215.         node_deleted->m_val = next_node->m_val;  
  216.         node_deleted->next = next_node->next;  
  217.   
  218.         delete next_node;  
  219.         next_node = NULL;  
  220.     }  
  221.     //链表中只有一个节点  
  222.     else if(*head == node_deleted){  
  223.         delete node_deleted;  
  224.         node_deleted = NULL;  
  225.         *head = NULL;  
  226.     }  
  227.     //要删除的节点是尾节点  
  228.     else{  
  229.         link_list_t node = *head;  
  230.         while(node->next != node_deleted)  
  231.             node = node->next;  
  232.   
  233.         node->next = node_deleted->next;  
  234.         delete node_deleted;  
  235.         node_deleted = NULL;  
  236.     }  
  237.   
  238.     return;  
  239. }  
  240.   
  241. //函数:获得链表中的倒数第K个节点  
  242. link_list_t get_kth_node(link_list_t head,int k){  
  243.     //性能:只需遍历链表一遍即可  
  244.     //算法思想:设置两个指针,一个指向链表头部,一个指向第k个节点,然后两个指针同时向后移动,当第二个指针指向链表的尾节点时,第一个指针指向的节点便是倒数第K个节点  
  245.     //注意代码的鲁棒性,防止程序的崩溃  
  246.     if(NULL == head || k <= 0)  
  247.         return NULL;  
  248.   
  249.     //设置两个指针  
  250.     link_list_t p1 = head,p2 = head;  
  251.     int i = 0;  
  252.     //第二个指针向前走k-1步  
  253.     while(i < k - 1 && p2->next != NULL){  
  254.         p2 = p2->next;  
  255.         ++i;  
  256.     }  
  257.     //注意链表中总节点数小于K的情况  
  258.     if(i != k - 1 && NULL == p2->next)  
  259.         return NULL;  
  260.   
  261.     //两个指针同时向后前进  
  262.     while(p2->next != NULL){  
  263.         p1 = p1->next;  
  264.         p2 = p2->next;  
  265.     }  
  266.   
  267.     return p1;  
  268. }  
  269.   
  270.   
  271. //函数:反转链表  
  272. //返回值:反转之后的链表头节点  
  273. link_list_t reverse_linklist(link_list_t head){  
  274.     //链表为空或者只有一个节点  
  275.     if(NULL == head || NULL == head->next)  
  276.         return head;  
  277.   
  278.     link_list_t prev_node = NULL,next_node,cur_node = head,head_reverse;  
  279.     while(cur_node != NULL){  
  280.         next_node = cur_node->next;  
  281.         if(NULL == next_node)  
  282.             head_reverse = cur_node;//原链表尾节点即逆转后链表的头节点  
  283.         cur_node->next = prev_node;  
  284.         prev_node = cur_node;  
  285.         cur_node = next_node;  
  286.     }  
  287.   
  288.     return head_reverse;  
  289. }  
  290.   
  291. //函数:删除链表中数据值等于给定值的节点  
  292. void delete_node(link_list_t *head,int val){  
  293.     if(NULL == head){  
  294.         cout << "Delete node failed :The node to be delete not exist!" << endl;  
  295.         return;  
  296.     }  
  297.   
  298.     if(val == (*head)->m_val){  
  299.         link_list_t node = *head;  
  300.         *head = (*head)->next;  
  301.         delete node;  
  302.         return;  
  303.     }  
  304.     //首先判断该节点是否存在链表中  
  305.     link_list_t node = *head;  
  306.     while(node->next != NULL){  
  307.         if(val == node->next->m_val)  
  308.             break;  
  309.         node = node->next;  
  310.     }  
  311.     //存在满足条件的节点  
  312.     if(node->next != NULL){  
  313.         link_list_t node_delete = node->next;  
  314.         node->next = node_delete->next;  
  315.         delete node_delete;  
  316.     }  
  317.     else  
  318.         cout << "删除失败:链表中不存在值等于" << val << "的节点" << endl;  
  319.   
  320.     return;  
  321. }  
  322.   
  323. //函数:合并两个已排序的链表(递归方法实现)  
  324. link_list_t merge_linklist_recursive(link_list_t head1,link_list_t head2){  
  325.     if(NULL == head1)  
  326.         return head2;  
  327.     else if(NULL == head2)  
  328.         return head1;  
  329.   
  330.     link_list_t merge_head = NULL;  
  331.   
  332.     if(head1->m_val < head2->m_val){  
  333.         merge_head = head1;  
  334.         merge_head->next = merge_linklist_recursive(head1->next,head2);  
  335.     }  
  336.     else{  
  337.         merge_head = head2;  
  338.         merge_head->next = merge_linklist_recursive(head1,head2->next);  
  339.     }  
  340.   
  341.     return merge_head;  
  342. }  

测试平台：WIn8+Ubuntu12.04+Vim+G++：



运行结果：

本文转载自CSDN博客博主江南烟雨原创文章，博客原文地址：http://blog.csdn.net/xiajun07061225/article/details/9246573


本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

就业指导

数据结构

算法

面试

c

笔试面试常考数据结构-单链表常用操作编程实现 的相关文章

随机推荐

  • C++11中 std::bind 的两种用法

    概述 std bind的头文件是

  • hadoop环境搭建之关闭防火墙和SELinux

    每一台服务器上都要做1 2 1 关闭防火墙 查看防火墙状态 systemctl status firewalld 关闭防火墙 systemctl disable firewalld systemctl stop firewalld 查看防火

  • iOS 获取系统键盘UIKeyboard方法

    公司项目需求 需要让弹窗显示在键盘所在的图层之上 而不是在弹窗出现的时候消失 如图1 系统弹窗出现的时候会使键盘暂时不显示 而这种效果显然不符合要求的 由于没想到更好的办法 只好从键盘自身的UIKeyboard做文章了 通过获取当前键盘的U

  • 【Java多线程批量数据导入的方法】

    前言 当遇到大量数据导入时 为了提高处理的速度 可以选择使用多线程来批量处理这些处理 常见的场景有 大文件导入数据库 这个文件不一定是标准的CSV可导入文件或者需要在内存中经过一定的处理 数据同步 从第三方接口拉取数据处理后写入自己的数据库

  • 按装完mysql怎么启动_mysql安装完怎么启动服务器？

    mysql安装完启动服务器的方法 1 打开 开始 菜单 依次点击 管理工具 服务 打开系统服务窗口 2 在 服务 窗口中找到 MySQL 右击选择 启动 命令就可以启动mysql服务器了 mysql 是世界流行的开源数据库系统 下面本篇文章

  • 关于TypeScript和React的使用

    TS和React的使用 接口与类型 type与interface 内置的语法糖 Partial和Required Readonly Omit Exclude 继承 接口与类型 type与interface 内置的语法糖 Partial和Re

  • ffmpeg错误码

    cpp view plain copy AVERROR BSF NOT FOUND 1179861752 AVERROR BUG 558323010 AVERROR DECODER NOT FOUND 1128613112 AVERROR

  • 数字化转型中的国产化替代之路

    引言 数字经济浪潮席卷全球 我国数字经济已进入快速发展阶段 加快推进企业数字化转型 已成为共识 同时有利于构建全产业链数字化生态 增强产业链上下游的自主可控能力 为数字经济社会发展 构建数智化生态注入新动能 在此过程中 国产软件企业作为数字

  • python利用tushare下载数据并计算当日收益率

    python利用tushare下载数据并计算当日收益率 计算股票收益率的程序主要有以下几部分构成 1 获取股票接口数据函数 pro daily stock 2 计算收益率函数 cal stock 里面有两种计算式 你可以根据自己字典写入建仓

  • 堆排序的topk问题+归并排序+六大排序总结

    回忆一下堆排序 思路 sift函数 调整 将父亲和孩子 左孩子和右孩子中最大的那个数 然后和父亲比较 如果孩子大就将孩子的位子变为下一个父亲 往下拉 并且将孩子的值赋给他的父亲 j lt high 条件认可 防止父亲在最后一层 魔法般的对应

  • Tensorflow的Win10、CPU版本安装

    1 Anaconda的安装 Miniconda的安装 Anaconda的安装链接 https www anaconda com products distribution 如图所示 点击箭头所指 可以安装anaconda的最新版本 Mini

  • elementui 禁止浏览器自动填充用户名密码

    浏览器这功能在登录的时候挺好用的 但是在注册和管理的时候就很难受了 所以 在普通的input上直接off就行了

  • 华为虚拟机服务器怎么使用教程,虚拟机装服务器教程

    虚拟机装服务器教程 内容精选 换一换 应用容器化改造有三种方式 您可单击这里查看 本教程以某游戏为例 将该游戏进行微服务的架构改造 再进行容器化 本教程不对改造细节做深度讲解 仅讲解大致的建议 如需要详细了解容器化改造的过程 请单击服务咨询

  • 攻防世界adworld-hit-the-core

    hit the core 题目来源 CTF 题目描述 暂无 题目附件 下载附件 kwkl kwkl strings home kwkl 桌面 8deb5f0c2cd84143807b6175f58d6f3f core CORE code c

  • 【视频流上传播放功能】前后端分离用springboot-vue简单实现视频流上传和播放功能【详细注释版本，包含前后端代码】

    前言 我是前端程序猿一枚 不是后端的 如有写的有不规范的地方别介意哈 自己摸索了两天算是把这个功能做出来了 网上看了很多帖子没注释说实话 我看的基本是懵逼的 毕竟没有系统学过 所以现在做出来了就总结一下 自己多写点注释解释一下逻辑 让前端的

  • SpringBoot+MyBatisPlus+Thymeleaf+AdminLTE增删改查实战

    说明 AdminLTE是网络上比较流行的一款Bootstrap模板 包含丰富的样式 组件和插件 非常适用于后端开发人员做后台管理系统 因为最近又做了个后台管理系统 这次就选的是AdminLTE做主题模板发现效果不错 这里我把最核心的Spri

  • 华为机考练习python

    HJ108 求最小公倍数 while True try a b map int input split for i in range 1 b 1 if a i b 0 print a i break except break HJ107 求

  • linux中256错误,YUM安装遭遇: [Errno 256] No more mirrors to try

    把YUM配置好后 使用yum命令进行安装时 出现了如下错误 Downloading Packages ftp 192 168 220 46 RHEL6 2 x64 Server libaio devel 0 3 107 10 el6 x86

  • Calling a v8 javascript function from c++ with an argument

    Calling a v8 javascript function from c with an argument up vote 18 down vote favorite 8 I am working with c and v8 and

  • 笔试面试常考数据结构-单链表常用操作编程实现

    单链表是笔试以及面试手写代码中常考的数据结构之一 下面实现了单链表的常见操作 创建单链表 删除节点 打印单链表 包括正向打印以及逆向打印 反转单链表 找出单链表的倒数第K个节点 合并两个有序单链表等操作 代码 C cpp view plai

热门标签