数据结构有哪些类型和特点？

本文共计1666个文字，预计阅读时间需要7分钟。

铁子们，最近有点忙啦！读了好多书，几乎没时间来写博客了！今天难得有空，特别想推出一篇博客。也许会有一篇，甚至两篇也说不好呢！好了，咱们回归正题吧！

铁子们，最近有些忙了！！读了很多书，几乎没有时间来写博客了！！今天，难得有空！！特别精心推出一篇博客也可能会有两篇也说不准！！

好了，我们回归正题吧！！

今天，为大家讲解三道单链表的OJ题！！

1.输入两个单链表，返回它们的公共交点

代码如下 :>

/* typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; */ SLTNode* Common_Point(SLTNode* List_01,SLTNode* List_02) { int lenA = 0; int LenB = 0; SLTNode* cur1 = List_01; SLTNode* cur2 = List_02; while(cur1) { lenA++; cur1 = cur1 ->next; } while(cur2) { lenB++; cur2 = cur2 ->next; } int gap = abs(lenA - lenB); //数学库调用绝对值“abs” SLTNode* longList = list_01; SLTNode* shortList = list_02; whlie(gap--) { longList = longList ->next; } if(lenA < lenB) { longList = List_02; shortList = List_01; } while(longList && shortList) { if(longList == shortList) { return longList; } else { shortList = shortList ->next; longList = longList ->next; } } return NULL; }

本道题的解题思路 :>

切入点是什么？ -----> 公共交点的地址相同

显然，我们要找到这个地址相同的结点，这就用到了指针！！

在指针行进的过程中，还要考虑到指针能走的范围有限定，即不能“逾越单链表的有效长度”！！

于是为了方便讲述以上代码，特别在VS上重新写了一遍，毕竟有颜色和没有颜色的视觉感是不同的！！

如下 :>

这样观感或许舒服了一些。

当求出两个链表的长度之后，由于不确定哪一个更长些，需要调用数学库“math.h”里的绝对值“abs”进行求取长度

之后，我们先让长的那个链表先走差距步“gap”,之后再让两个链表再同时行进！！

这样我们就可以，找出那个公共交点了！！

这部分的代码，循环体条件可以写一个就可以了！！

为了方便加深理解，下面图示会更加清晰 :>

下面的两个单链表长度不一，他们的差距步是1，则先让长的那个链表的头指针先走，那么走后如下所示 :>

longList此时位于了 2 的结点处！！

那么接下来，两个单链表的指针同时走，仅仅再走一步，就可以找到我们的公共交点了！！

另外，请注意 ::> longList == shortList 的意思是，它们的地址相同！！这样就找到了！！

本题到此结束，下面请看第二道OJ题目

2.判断一个链表是否有环

显然，出现了“判断”以及“环”两个关键字！！】

显然要到布尔判断“bool”, 不过别忘了包含头文件 <stdbool.h>

本题的思路很简单，快慢指针即可！！

下面上手代码 :>

/* typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; */ //布尔判断单链表是否有环 bool hasCycle(SLTNode* phead) { SLTNode* slow = phead; SLTNode* fast = phead; while(fast && fast ->next) { slow = slow ->next; fast = fast ->next ->next; if(fast == slow) return true; } return false; }

为了视觉上舒服一些，再放一张有颜色的代码吧！！

针对循环体的条件 :>

为了方便理解，再上一张图示解析 ::

以上三种样式符合，条件 fast ->next

而还有一个有条件 fast 那么该作何理解呢？

显然此种情况适用于空链表 这显然是一种特殊情况，必须要考虑的

单链表OJ题的第二道题目结束了，下面请看第三道题目，逻辑上更加严谨一些

3.环形链表

给定一个链表的头结点 head , 返回链表开始入环的第一个结点。如果链表无环，则返回 NULL 。

本题相较于刚刚讲解的第二道题目，可谓是换汤不换药！！

思路如下 :>

显然还是要用到快慢指针，找到入环的第一个结点，就是那个第一节点的地址并且返还就可以了！！

不过，显然还有一些特殊情况需要考虑！！

比如，空链表， 一个节点

现在上手代码 :>

/* typedef int SLTDataType; typedef struct SListNode { SLTDataType data; struct SListNode* next; }SLTNode; */ //寻找单链表入环的第一个结点 void detectCycle(SLTNode* head) { SLTNode* slow = head; SLTNode* fast = head; while(fast != NULL) { slow = slow ->next; if(fast ->next == NULL) return NULL; fast = fast ->next ->next; //快慢指针第一次相遇 if(fast == slow) { SLTNode* ptr = head; while(ptr != slow) { ptr = ptr ->next; slow = slow ->next; } return ptr; } } return NULL; }

为了视觉上舒服一些，再放一张有颜色的代码吧！！

现对以上代码，进行图示解析，这样可以方便理解 ！

起始点 ---> 相遇点

此后，在设置一个新的指针 ptr

显然如上图所示，当 slow 指针 与 ptr 指针再行进一步之后，两者的地址第一次相同，此时返回 ptr 指针就是我们要寻找的开始入环的第一个结点！！

注意，此题很容易让人误判 7 才是入环的第一个结点！！

这里引用一句话 “圆没有端点”

循环条件 fast != NULL 是考虑了空链表的情况，如果是空链表，直接跳出大循环体，返回 NULL

而以下部分的代码是考虑 只有一个节点的情况：

本题不考虑一个单节点构成环，在OJ题当中，此种情况的索引位置是 -1，即 默认该种情况下，不存在环

至此，本期的单链表OJ题已经讲解完了！！感谢阅读！！愿共同进步！！