数据结构-->单链表OJ题--->讲解_06

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

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

今天，为大家讲解三道单链表的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题已经讲解完了！！感谢阅读！！愿共同进步！！