AI 助理
备案控制台
开发者社区 人工智能 文章 正文

C语言中链表经典面试题目

2023-05-12 105
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 链表分割链表的回文结构 相交链表

🚀🚀🚀大家觉不错的话，就恳求大家点点关注，点点小爱心，指点指点🚀🚀🚀

目录

链表分割

链表的回文结构

相交链表

 

链表分割

描述

现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。

自测输入:

       {1,1,3,2,4},2

实际输出

       {1,1,3,2,4}

自测输入:

       {1,1,3,1,4},2

实际输出

       {1,1,1,3,4}

解题思路：

整体思路是，创建两个头指针head和phead，head连接小于x的节点，phead连接大于等于x的节点，最后head连接的尾节点指向phead连接的头节点。

1. class Partition
2. {
3. public:
4. ListNode* partition(ListNode* pHead, int x) 
5.     {
6. if(pHead==NULL)
7.         {
8. return NULL;
9.         }
10. // write code here
11.         ListNode* head=NULL;
12.         ListNode* n1=NULL;
13.         ListNode* phead=NULL;
14.         ListNode* n2=NULL;
15.         ListNode* cur=pHead;
16. while(cur)
17.         {
18. if(cur->val<x)
19.             {
20. if(head==NULL)
21.                 {
22.                     head=n1=cur;
23.                 }
24. else
25.                 {
26.                     n1->next=cur;
27.                     n1=n1->next;
28.                 }
29.                 cur=cur->next;
30.             }
31. else
32.             {
33. if(phead==NULL)
34.                 {
35.                     phead=n2=cur;
36.                 }
37. else
38.                 {
39.                    n2->next=cur;
40.                    n2=n2->next;
41.                 }
42.                 cur=cur->next;
43.             }
44.         }
45. if(n2!=NULL)
46.         {
47.             n2->next=NULL;
48.         }
49. if(head==NULL)
50.         {
51. return phead;
52.         }
53.         n1->next=phead;
54. return head;
55.     }
56. };

链表的回文结构

描述

对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。

给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。

测试样例：

1->2->2->1

返回：true

解题思路：

找到链表的中间节点，然后将中间节点包括以后的节点进行逆置，逆置后得到一个头指针，然后依次判断原头指针连接的节点的值和现在得到的头指针连接的节点的值进行比较。这里不需要担心，链表的节点数的奇偶性。

1. #include <cstddef>
2. class PalindromeList {
3. public:
4. bool chkPalindrome(ListNode* A)
5.      {
6. // write code here
7.         ListNode* cur=A;
8. int count =0;
9. while(cur)
10.         {
11.             cur=cur->next;
12.             count++;
13.         }
14. int num=count/2;
15.         ListNode* tail=A;
16.         ListNode* prev=NULL;
17.         ListNode* head=NULL;
18.         ListNode* n1=A;
19. while(num)
20.             {
21.                 num--;
22.                 tail=tail->next;
23.             }
24.             n1=tail;
25.             prev=tail->next;
26. while(n1)
27.             {
28.                 n1->next=head;
29.                 head=n1;
30.                 n1=prev;
31. if(prev!=NULL)
32.                 {
33.                     prev=prev->next;
34.                 }
35.             }
36. while(head)
37.             {
38. if(A->val!=head->val)
39.                 {
40. return false;
41.                 }
42.                 head=head->next;
43.                 A=A->next;
44.             }
45.             tail=NULL;
46. return true;
47.     }
48. };
49. 
50. 
51. 这里是将原来的，找中间节点和逆置的函数进行复用
52. // #include <cstddef>
53. // class PalindromeList {
54. // public:
55. // struct ListNode* reverseList(struct ListNode* head)
56. // {
57. //     if(head==NULL)
58. //     {
59. //         return NULL;
60. //     }
61. //     struct ListNode* n1=NULL;
62. //     struct ListNode* n2=head;
63. //     struct ListNode* n3=head->next;
64. //     while(n2)
65. //     {
66. //         n2->next=n1;
67. //         n1=n2;
68. //         n2=n3;
69. //         if(n3!=NULL)
70. //         {
71. //             n3=n3->next;
72. //         }
73. //     }
74. //     return n1;
75. // }
76. // struct ListNode* middleNode(struct ListNode* head)
77. // {
78. //     struct ListNode* cur=head;
79. //     int count=0;
80. //     while(cur)
81. //     {
82. //         cur=cur->next;
83. //         count++;
84. //     }
85. //     int num=count/2;
86. //     cur=head;
87. //     while(num--)
88. //     {
89. //         cur=cur->next;
90. //     }
91. //     return cur;
92. // }
93. // bool chkPalindrome(ListNode* A)
94. //    {
95. //         // write code here
96. //         ListNode* mid=middleNode(A);
97. //         ListNode* remid=reverseList(mid);
98. //         while(remid)
99. //         {
100. //             if(A->val!=remid->val)
101. //             {
102. //                 return false;
103. //             }
104. //             A=A->next;
105. //             remid=remid->next;
106. //         }
107. //         return true;
108. //    }
109. // };

相交链表

 

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

CDC3B817-6ADF-4852-B2F2-541E1DF67D03.png

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

  • intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
  • listA - 第一个链表
  • listB - 第二个链表
  • skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
  • skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

 

示例 1：

214D2CC8-56F9-4AC8-9972-7BB86683298D.png

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3

输出：Intersected at '8'

解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。

从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,6,1,8,4,5]。

在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

— 请注意相交节点的值不为 1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点) 是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点) 在内存中指向相同的位置。

 

示例 2：

6672629F-9563-43D8-975D-B0B656CCCCB6.png

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1

输出：Intersected at '2'

解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。

从各自的表头开始算起，链表 A 为 [1,9,1,2,4]，链表 B 为 [3,2,4]。

在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

示例 3：

8D3C3149-8D7D-4ACD-8266-A3477A3DB40A.png

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2

输出：null

解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。

由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。

这两个链表不相交，因此返回 null 。

 

提示：

  • listA 中节点数目为 m
  • listB 中节点数目为 n
  • 1 <= m, n <= 3 * 104
  • 1 <= Node.val <= 105
  • 0 <= skipA <= m
  • 0 <= skipB <= n
  • 如果 listA 和 listB 没有交点，intersectVal 为 0
  • 如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

 

进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？

解题思路：

判断两个链表是否相交的关键在于，两个链表的尾节点是否相等（这里指的是为节点的地址，而不是值），相等的话，则两个链表必定相交。如果相交的话，就需要找交点，找交点有两种方法，第一种（暴力求解）：A链表所有节点跟B链表的所有节点比较一遍，相等的就是交点，但是时间复杂度为O(N*M)。第二种：分别得到两个链表的长度LA和LB，长的先走abs(LA-LB)步，然后两个同时走，第一个相等的就是交点。

1. //判断链表是否相交，重点在于判断节点的地址是否相等
2. struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
3. {
4. struct ListNode* tail1=headA;
5. struct ListNode* tail2=headB;
6. int lenA=1,lenB=1;
7. while(tail1->next)
8.   {
9.       tail1=tail1->next;
10.       lenA++;
11.   }
12. while(tail2->next)
13.   {
14.       tail2=tail2->next;
15.       lenB++;
16.   }
17. //如果尾节点不相等，一定不相交
18. if(tail1!=tail2)
19.   {
20. return NULL;
21.   }
22. //长先走差距步
23. int gap=abs(lenA-lenB);
24. struct ListNode* longList=headA;
25. struct ListNode* shortList=headB;
26. if(lenA<lenB)
27.   {
28.       longList=headB;
29.       shortList=headA;
30.   }
31. while(gap--)
32.   {
33.       longList=longList->next;
34.   }
35. while(longList!=shortList)
36.   {
37.       longList=longList->next;
38.       shortList=shortList->next;
39.   }
40. return longList;
41. }

 

🌸🌸🌸如果大家还有不懂或者建议都可以发在评论区，我们共同探讨，共同学习，共同进步。谢谢大家！ 🌸🌸🌸  



文章标签：
C语言
算法
关键词：
C语言链表
链表c语言
C语言题目
链表题目
面试题目
游客fcyapbbxkxpio
目录
相关文章
LuckiBit
|
21天前
|
存储 算法 C语言
【C语言】深入浅出：C语言链表的全面解析
链表是一种重要的基础数据结构，适用于频繁的插入和删除操作。通过本篇详细讲解了单链表、双向链表和循环链表的概念和实现，以及各类常用操作的示例代码。掌握链表的使用对于理解更复杂的数据结构和算法具有重要意义。
LuckiBit
170 6
龙大吉
|
24天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
45 5
ephemerals__
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
87 4
禁默
|
2月前
|
存储
链表题目练习及讲解（下）
链表题目练习及讲解（下）
禁默
31 9
可惜已不在
|
2月前
|
程序员 C语言
【C语言】LeetCode(力扣)上经典题目
【C语言】LeetCode(力扣)上经典题目
可惜已不在
41 1
禁默
|
2月前
链表题目练习及讲解（上）
链表题目练习及讲解（上）
禁默
30 1
c的前世今生
|
2月前
|
存储 缓存 C语言
C语言：链表和数组有什么区别
C语言中，链表和数组是两种常用的数据结构。数组是一种线性结构，元素在内存中连续存储，通过下标访问，适合随机访问且大小固定的情况。链表由一系列不连续的节点组成，每个节点存储数据和指向下一个节点的指针，适用于频繁插入和删除操作的场景，链表的大小可以动态变化。
c的前世今生
34 2
ephemerals__
|
1月前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
61 0
吞吞吐吐的
|
C语言 编译器 图形学
几道C语言题目
吞吞吐吐的
828 0
LuckiBit
|
21天前
|
存储 C语言 开发者
【C语言】字符串操作函数详解
这些字符串操作函数在C语言中提供了强大的功能，帮助开发者有效地处理字符串数据。通过对每个函数的详细讲解、示例代码和表格说明，可以更好地理解如何使用这些函数进行各种字符串操作。如果在实际编程中遇到特定的字符串处理需求，可以参考这些函数和示例，灵活运用。
LuckiBit
40 10

热门文章

最新文章

  • 1
    C# 面试题解析-请遍历页面上所有的TextBox控件并给它赋值为string.Empty
  • 2
    面试官：ZGC 原理是什么，它为什么能做到低延时？
  • 3
    面试题1：赋值运算符函数
  • 4
    大厂高频面试真题详解：最长无重复字符的子串
  • 5
    【求职英语】一些英语面试题整理
  • 6
    都2022年了，Python继续霸榜，SQL写得溜，面试或能加分
  • 7
    java面试强基（1）
  • 8
    2022 前端一场面试及答案整理
  • 9
    软件测试面试题：性能测试的流程?
  • 10
    软件测试面试题：请讲一讲析构函数和虚函数的用法和作用？
  • 1
    Android技能树 — 数组,链表,散列表基础小结，android教程零基础入门
    49
  • 2
    单链表的习题练习（温故而知新）
    47
  • 3
    关于带环链表的结论
    33
  • 4
    数据结构链表详解(不仅顺序表可以，我链表也可以)
    45
  • 5
    链表的头插法和尾插法
    254
  • 6
    序表和链表的区别（通俗易懂）
    60
  • 7
    特殊链表（循环单链表，循环双链表，静态链表）
    58
  • 8
    双链表的插入，删除以及遍历
    52
  • 9
    实现双向链表的运势解读
    42
  • 10
    实现双向链表计算运势
    44

    • 相关课程

    更多
  • 你的第一门C语言课
  • C语言学习教程
  • Java面试疑难点解析 - 面试技巧及语言基础
  • Java面试疑难点解析 - Java Web开发
  • Java面试疑难点解析 - 系统架构及项目设计
  • Go语言核心编程 - 数据结构和算法

    • 相关电子书

    更多
  • 阿里云技术面试红宝书
  • 超全算法笔试-模拟题精解合集
  • 程序员面试宝典
    • 下一篇
    DataWorks售前咨询