【初阶数据结构与算法】链表刷题之链表分割、相交链表、环形链表1、环形链表I、环形链表II

一、链表分割

题目链接：https://www.nowcoder.com/practice/0e27e0b064de4eacac178676ef9c9d70

   我们来看看链表分割的题目描述和它给出的函数：

   这个题虽然是以C++形式来做，但是不用担心，我们知道在哪里写代码就可以了，就是题目提示的地方，这个属于C++类的知识，我们在后面的C++部分会详细介绍
   接着我们回归正题，题目要求我们将链表分割开来，值小于x的节点要放在链表的左边，值大于等于x的节点要放在链表的右边，这个题该怎么做呢？
   方法和双指针的算法有点类似，但是又不完全相同，我们可以创建两个新链表，一个存放比x小的节点，另一个存放比x大或者和x相等的节点，最后让小链表和大链表首位相连即可
   这里我们要注意的是，如果我们创建的两个链表初始为空会发生什么，我们每次插入节点时，都要判断要插入的链表是否为空，空和非空的操作不一致，加上我们有两个新链表，操作起来更加的繁琐
   所以我们还是用上之前学过的知识，怎么保证一个链表默认不为空？没错，就是在初始情况下创建一个哨兵位节点占位，它不存放有效的数据，单纯用来占位，这样我们在插入节点时就不需要去判断链表是否为空了
   最后我们再来大致梳理一下解题思路，就是创建大小链表，同时创建哨兵位占位，然后遍历原链表，把值小于x的节点放在小链表，其它的放在大链表，最后让小链表和大链表首尾相连即可，题解如下：

ListNode* partition(ListNode* pHead, int x) {ListNode* lesshead, *lesstail;ListNode* greaterhead, *greatertail;lesshead = lesstail = (ListNode*)malloc(sizeof(ListNode));greaterhead = greatertail = (ListNode*)malloc(sizeof(ListNode));ListNode* pcur = pHead;while(pcur){if(pcur->val < x){lesstail->next = pcur;lesstail = pcur;}else {greatertail->next = pcur;greatertail = pcur; }pcur = pcur->next;}//小链表的尾巴连接大链表的头//大链表哨兵位的下一个节点是真正的头lesstail->next = greaterhead->next;//为了避免形成环，把尾节点的next指针置为空greatertail->next = NULL;//要返回的头就是小链表哨兵位后真正的头ListNode* ret = lesshead->next;//资源清理工作free(lesshead);free(greaterhead);lesshead = NULL;greaterhead = NULL;return ret;}

   我们提交一下试试：

二、相交链表

题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

   我们来看看题目描述和给出的函数：


   题目的要求就是给我们两个链表，然后让我们判断这两个链表是否相交，如果相交就返回相交的节点，否则就返回空
   我们要注意到相交链表的特殊性，直线相交的话它们还会朝着不同的方向继续延伸，想象一下链表相交以后会怎么样，它们相交后一定只有一个方向，而不会像直线相交那样有多个方向，因为如果它们相交，那么相交节点的next指针指向同一个节点，如此循环下去自然就只有一个方向
   那么问题好像要简单一些了，我们遍历两个链表，看看有没有相同的节点不就好了，可是还是有一个问题，我们看看题目的第一个示例就知道了：

   这个问题就是两个链表的长度可能不同，在上面的示例中，如果同时开始遍历的话，当链表A遍历到相交节点8时，链表B才遍历到节点1，这样它们差一位就永远不能相等，也就找不到相交节点
   那有没有什么办法让它们从同一起跑线出发呢？我们能让小的那个链表变长，但是可以让大链表往前走两步呀，比如上图，我们就可以让大链表先往前走一步到6节点，然后它们在同一起跑线往后遍历就可以找到相交节点了
   问题是我们要怎么知道那个链表大，大多少，知道了这两个条件后，我们就可以让大链表提前走它们的长度差距，然后同时对他们进行遍历，为了知道它们的大小，我们可以定义两个整型计数器来计算它们的大小
   然后根据大小来判断谁大谁小，然后让大链表往前走它们的长度差距，最后让大小链表同时往前遍历，如果遇到相同的节点说明它们相遇了，返回这个节点就可以了，但是如果遍历到尾结点后还没有相同的节点，说明两个链表不相交，返回空，题解如下：

typedef struct ListNode ListNode;
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{//创建两个节点指针遍历链表ListNode* pcurA = headA;ListNode* pcurB = headB;int countA = 0, countB = 0;while(pcurA){countA++;pcurA = pcurA->next;}while(pcurB){countB++;pcurB = pcurB->next;}//假设法来判断链表大小//假设A链表更小//如果假设错误后面计算出大小后进行修改ListNode* lesslist = headA;ListNode* greaterlist = headB;//如果A的节点个数大于B，那么进行修改if(countA > countB){lesslist = headB;greaterlist = headA;}//接着让大的链表往后走间隔大小//首先使用绝对值函数求间隔大小int size = abs(countA - countB);while(size--){greaterlist = greaterlist->next;}//此时两个链表在同一起跑线，长度一样//然后再往后遍历while(lesslist){if(lesslist == greaterlist){return lesslist;}lesslist = lesslist->next;greaterlist = greaterlist->next;}//出了循环说明没有相交，返回NULLreturn NULL;
}

   最后提交一下代码：

三、环形链表I

题目链接：https://leetcode.cn/problems/linked-list-cycle/description/

   我们来看看环形链表I的题目描述与示例：

   我们首先要知道链表带环是什么意思，就是它的尾结点的next指针不指向空了，而是指向链表中的某个节点，以此成为带环链表
   这个题还较为简单，只需要我们判断链表是否有环，而不需要我们找出入环节点，做这个题需要用到一个结论，这里我就直接说出来了，如果对它的证明过程感兴趣可以自行去了解一下，当然也可以私信我，我会及时给出解答，这里就不多证明了
   在这里我们需要用到快慢指针，结论就是慢指针一次走一步，快指针一次走两步，如果链表带环，那么快指针和慢指针一定会在环内相遇，如果不带环那么循环直接结束了，有了这个结论我们写起来就简单多了，如下：

typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) 
{ListNode* slow = head;ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){return true;}}return false;
}

   我们提交代码试试：

四、环形链表||

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/

   我们来看看环形链表II的题目描述和示例：


   这个题和上一个题的最大区别就是，这个题不仅要求我们判断链表是否是一个带环链表，如果带环还要我们找出入环的第一个节点，这个就比较难了
   这里我们还是使用一个结论，相关的证明可以自行了解，也可以私信我，我会及时给出解答，这里就不多证明了
   结论还是需要用到快慢指针，如果链表带环，那么快慢指针一定就会在环内相遇，并且相遇节点到入环节点的距离，和头结点到入环节点的距离相等
   通俗一点说就是，当快慢指针在环内相遇后，让头结点和慢指针同时往前，并且每次走一步，那么当头结点和慢指针相遇时，相遇节点就是入环节点
   因为此时头结点和慢指针走的步数相同，还相遇了，根据上面的结论就可以说明相遇节点就是入环节点，是不是特别神奇，接着我们就根据这个结论来写代码，如下：

typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) 
{ListNode* slow = head;ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){//进入这里说明链表带环ListNode* pcur = head;while(pcur){//判断是否相等//不相等循环的往前走if(pcur == slow){return pcur;}pcur = pcur->next;slow = slow->next;}}}//出了循环，说明链表不带环return NULL;
}

   提交代码：

   那么今天的刷题分享就到这里啦，如果有什么疑问欢迎提出，题目中使用的相关证明也可以直接问我
   最后感谢大家的观看，bye~