经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置：技术经验 » 程序设计 » C 语言 » 查看文章
C语言实题讲解快速掌握单链表上
来源：jb51　　时间：2022/4/11 16:15:58　　对本文有异议

1、移除链表元素

链接直达：

移除链表元素

题目：

思路：

此题要综合考虑多种情况，常规情况就如同示例1，有多个节点，并且val不连续，但是非常规呢？当val连续呢？当头部就是val呢？所以要分类讨论

常规情况：

需要定义两个指针prev和cur，cur指向第一个数据，prev指向cur的前一个。依次遍历cur指向的数据是否为val，若是，则把prev的下一个节点指向cur的下一个节点上，cur=cur->next，prev跟着cur一起走，直到cur走到NULL

连续val：

当我们仔细观察下，不难发现，在常规情况下是可以解决连续val的，但是头部val就不可了

头部val：

此时除了刚才定义的两个指针prev和cur外，还要有个head指向头部，当头部是val时，将cur指向下一个位置，head跟着一起动，直到cur指向的数据不为val时，将head赋给prev。此时剩余的就按常规处理即可。

代码如下：

  1. struct ListNode* removeElements(struct ListNode* head, int val){
  2.     struct ListNode*cur=head;
  3.     struct ListNode*prev=NULL;
  4.     while(cur)
  5.     {
  6.         if(cur->val!=val)
  7.         {
  8.             prev=cur;
  9.             cur=cur->next;
  10.         }
  11.         else
  12.         {
  13.             struct ListNode*next=cur->next;
  14.             if(prev==NULL)
  15.             {
  16.                 free(cur);
  17.                 cur=next;
  18.                 head=next;
  19.             }
  20.             else
  21.             {
  22.                 prev->next=cur->next;
  23.                 free(cur);
  24.                 cur=prev->next;
  25.             }
  26.         }
  27.     }
  28.     return head;
  29. }

2、反转链表

链接直达：

反转链表

题目：

思路：

法一：三指针翻转方向

定义三个指针n1，n2，n3分别用来指向NULL，第一个数据，第二个数据。让n2的next指向n1，把n2赋给n1，再把n3赋给n2，再执行n3=n3->next的操作，接下来重复上述操作，直到n2指向空即可。但是要注意，要先判断该链表是否为NULL，如果是，则返回NULL，此外，还要保证当n3为空时就不要动了，直接把n3赋给n2即可。

代码如下：

  1. struct ListNode* reverseList(struct ListNode* head){
  2.     if(head==NULL)
  3.     {
  4.         return NULL;
  5.     }
  6.     struct ListNode*n1=NULL;
  7.     struct ListNode*n2=head;
  8.     struct ListNode*n3=n2->next;
  9.     while(n2)
  10.     {
  11.         n2->next=n1;
  12.         n1=n2;
  13.         n2=n3;
  14.         if(n3)
  15.         {
  16.             n3=n3->next;
  17.         }
  18.     }
  19.     return n1;
  20. }

法二：头插

此法就需要再创建一个链表了，创建一个新的头部newhead指向NULL，再定义一个指针cur指向原链表第一个数据，注意还得定义一个指针next指向cur的下一个节点。遍历原链表，把节点取下来头插到newhead所在的链表。每次更新newhead赋给cur，如图所示：

 代码如下：

  1. struct ListNode* reverseList(struct ListNode* head){
  2.     if(head==NULL)
  3.     {
  4.         return NULL;
  5.     }
  6.     struct ListNode*cur=head;
  7.     struct ListNode*next=cur->next;
  8.     struct ListNode*newhead=NULL;
  9.     while(cur)
  10.     {
  11.         cur->next=newhead;
  12.         newhead=cur;
  13.         cur=next;
  14.         if(next)
  15.         {
  16.             next=next->next;
  17.         }
  18.     }
  19.     return newhead;
  20. }

3、链表的中间节点

链接直达：

链表的中间节点

题目：

 思路：

快慢指针

这道题要注意奇偶数，如果为奇数，如示例1，那么中间节点值就是3，反之偶数如示例2，返回第二个中间节点。此题我们定义两个指针slow和fast都指向第一个数据的位置，区别在于让slow一次走1步，fast一次走2步。当fast走到尾指针时，slow就是中间节点

 代码如下：

  1. struct ListNode* middleNode(struct ListNode* head){
  2.     struct ListNode*slow=head;
  3.     struct ListNode*fast=head;
  4.     while(fast&&fast->next)
  5.     {
  6.         slow=slow->next;
  7.         fast=fast->next->next;
  8.     }
  9.     return slow;
  10. }

4、链表中倒数第k个节点

链接直达：

链表中倒数第k个节点

题目：

 思路：

快慢指针

定义两个指针slow和fast，让fast先走k步，再让slow和fast同时走，当fast走到尾部时，slow就是倒数第k个，因为这样的话slow和fast的差距始终是k个，当fast走到空时结束。此题同样可以走k-1步，不过当fast走到尾部时结束，也就是fast的下一个节点指向空时结束，都一样。先拿走k步举例，如图所示：

 代码如下：

  1. struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
  2.     // write code here
  3.     struct ListNode*fast=pListHead;
  4.     struct ListNode*slow=pListHead;
  5.     while(k--)
  6.     {
  7.         //if判断，防止k大于链表的长度
  8.         if(fast==NULL)
  9.             return NULL;
  10.         fast=fast->next;
  11.     }
  12.     while(fast)
  13.     {
  14.         fast=fast->next;
  15.         slow=slow->next;
  16.     }
  17.     return slow;
  18. }

5、合并两个有序链表

链接直达：

合并两个有序链表

题目：

 思路：

法一：归并（取小的尾插）--- 带头节点

假设新链表的头叫head并指向NULL，还需要定义一个指针tail来方便后续的找尾，依次比较list1和list2节点的值，把小的放到新链表head上，并更新tail，再把list1或list2更新一下。当list1和list2两个链表中一个走到空时，直接把剩下的链表所有剩下的元素拷进去即可

 代码如下：

  1. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
  2.     //检查list1或list2一开始就为NULL的情况
  3.     if(list1==NULL)
  4.     {
  5.         return list2;
  6.     }
  7.     if(list2==NULL)
  8.     {
  9.         return list1;
  10.     }
  11.     struct ListNode*head=NULL;
  12.     struct ListNode*tail=head;
  13.     while(list1&&list2)
  14.     {
  15.         if(list1->val<list2->val)
  16.         {
  17.             if(tail==NULL)
  18.             {
  19.                 head=tail=list1;
  20.             }
  21.             else
  22.             {
  23.                 tail->next=list1;
  24.                 tail=list1;
  25.             }
  26.             list1=list1->next;
  27.         }
  28.         else
  29.         {
  30.             if(tail==NULL)
  31.             {
  32.                 head=tail=list2;
  33.             }
  34.             else
  35.             {
  36.                 tail->next=list2;
  37.                 tail=list2;
  38.             }
  39.             list2=list2->next;
  40.         }
  41.     }
  42.     //当list1和list2其中一个走到空的情况
  43.     if(list1==NULL)
  44.     {
  45.         tail->next=list2;
  46.     }
  47.     else
  48.     {
  49.         tail->next=list1;
  50.     }
  51.     return head;
  52. }

法二：哨兵位的头节点

解释下带头节点：

比如说同样一个链表存1，2，3。不带头节点只有这三个节点，head指向1。而带头节点的同样存3个值，不过有4个节点，head指向头部这个节点，这个节点不存储有效数据

 带头结点有如下好处，不用判断head和tail是否为空了，也不用判断list1和list2是否为空了，会方便不少。和上述思路一样，取小的下来尾插，直接链接到tail后面即可。但是要注意返回的时候要返回head的next，因为题目给的链表是不带头的，而head本身指向的就是那个头，所以要返回下一个。

代码如下：

  1. struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
  2.     struct ListNode* head = NULL, * tail = NULL;
  3.     head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
  4.     head->next = NULL;
  5.     while (list1 && list2)
  6.     {
  7.         if (list1->val < list2->val)
  8.         {
  9.             tail->next = list1;
  10.             tail = list1;
  11.             list1 = list1->next;
  12.         }
  13.         else
  14.         {
  15.             tail->next = list2;
  16.             tail = list2;
  17.             list2 = list2->next;
  18.         }
  19.     }
  20.     //当list1和list2其中一个走到空的情况
  21.     if (list1 == NULL)
  22.     {
  23.         tail->next = list2;
  24.     }
  25.     else
  26.     {
  27.         tail->next = list1;
  28.     }
  29.     struct ListNode* list = head->next;
  30.     free(head);
  31.     head = NULL
  32.         return list;
  33. }

6、链表分割

链接直达：

链表分割

题目：

 思路：

定义两个链表lesshead和greaterhead。遍历原链表，把 < x 的插入到链表1，把 > x 的插入到链表2，最后再把链表1和链表2链接起来。在定义两个尾指针以跟进链表1和2新增元素

 代码如下：

  1. class Partition {
  2. public:
  3.     ListNode* partition(ListNode* pHead, int x) {
  4.         // write code here
  5.         struct ListNode* lessHead, * lessTail, * greaterHead, * greaterTail;
  6.         lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
  7.         greaterHead = greaterTail = (struct ListNode*)malloc(sizeof(struct ListNode));
  8.         lessTail->next = greaterTail->next = NULL;
  9.         struct ListNode* cur = pHead;
  10.         while (cur)
  11.         {
  12.             if (cur->val < x)
  13.             {
  14.                 lessTail->next = cur;
  15.                 lessTail = lessTail->next;
  16.             }
  17.             else
  18.             {
  19.                 greaterTail->next = cur;
  20.                 greaterTail = greaterTail->next;
  21.             }
  22.             cur = cur->next;
  23.         }
  24.         //合并
  25.         lessTail->next = greaterHead->next;
  26.         greaterTail->next = NULL;
  27.         struct ListNode* list = lessHead->next;
  28.         free(lessHead);
  29.         free(greaterHead);
  30.         return list;
  31.     }
  32. };

到此这篇关于C语言实题讲解快速掌握单链表上的文章就介绍到这了,更多相关C语言 单链表内容请搜索w3xue以前的文章或继续浏览下面的相关文章希望大家以后多多支持w3xue！

 友情链接：直通硅谷 　点职佳 　北美留学生论坛

C 语言热门文章

  • 图形学入门(1)——直线生成算法（DDA和Bresenham）
  • 用C语言制作一个最简单的飞机游戏！
  • MODBUS 超时时间计算
  • zabbix wait for 15s seconds 出现原因及调优建议
  • C/C++知识分享：assert()函数
  • 图形学入门(2)——圆弧生成算法（中点画圆法）
  • C 共享内存封装
  • C语言中break与continue的用法和区别详解
  • GStreamer基础教程09 - Appsrc及Appsink
  • 三元组矩阵行列式的计算（用递归）

    • C 语言推荐文章

  • C语言指针易混淆知识点总结
  • 进程间通信
  • 数组降维、函数栈帧、地址空间、可变参数原理剖析
  • 【Learning eBPF-3】一个 eBPF 程序的深入剖析
  • [apue] 进程控制那些事儿
  • 解密C语言选择结构：掌握条件语句与分支逻辑的利器
  • 精通C语言：打造高效便捷的通讯录管理系统
  • c语言实现内存池
  • [数据结构] 数组与特殊矩阵
  • 探索C语言结构体：编程中的利器与艺术

    • 本站QQ群：前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

    W3xue 的所有内容仅供测试，对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
    关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接（目前9元/月）请联系QQ：27243702 沸活量
    皖ICP备17017327号-2　皖公网安备34020702000426号