环形链表和相交链表OJ题

在这里插入图片描述

这篇博客详细讲解了环形数组和相交数组的问题

文章目录

环形链表和相交链表OJ题
- 一、环形链表
- - e.g.1
  - e.g.2
- 二、相交链表

一、环形链表

环形列表是指尾结点next不指向NULL了，而是指向包括自己的前面任意一个结点。

e.g.1

题目及要求：
在这里插入图片描述

样例：

分析：

1.正常如果在找尾过程中，尾结点的下一个结点就是NULL,而环形链表则不是这样，所以我们可以通过这个条件来做一个初步的判断。
2.我们还是可以用快慢指针的思想（这个很重要，在很多找特定位置结点的题都可以用到这个思想），一个快指针和一个慢指针，如果相遇了，那就说明链表是一个循环的。快的可以给慢的扣圈。

代码实现：

bool hasCycle(struct ListNode *head) {struct ListNode* fast = head, *slow = head;while (fast && fast->next)//奇偶结点不同，判断条件不同{fast = fast->next->next;//快指针，后续会解释为什么用2倍速slow = slow->next;if (fast == slow)//相遇{return true;}}return false;
}

e.g.2

题目及要求：
在这里插入图片描述

样例：
在这里插入图片描述
分析：

结论：一个指针从起点，另一个指针从相遇点，他们同时出发，会在第一个进入循环的结点处相遇。
代码实现：

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* fast = head, *slow = head;while (fast && fast->next){fast = fast->next->next;slow = slow->next;if (fast == slow){struct ListNode* meet = slow;while (meet != head){head= head->next;meet = meet->next;}return head;}}return NULL;
}

二、相交链表

题目及要求：
在这里插入图片描述

样例：
在这里插入图片描述

在这里插入图片描述
分析：
只能Y型相交，不能X型，因为一个结点向后只能存储一个地址，所以用了一个之后，后面就都是共同的结点了。
首先，我们可以考虑用A的第一个结点去和B里面每一个结点的地址比较，切记不能比结构体里的数值，因为数值可以相等。再用第二个去比，持续循环，这样最差的情况就是都找一遍还没找到，时间复杂度O(n ^ 2)。
其次，我们想一点时间复杂度更低的方式，可以找到他们等长位置的结点，一起向后走就可以了，其实这里也用到了快慢指针的思想，快慢指针就是利用中间的差值，而我们是为了将差值消掉。
代码实现：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* tailA = headA, *tailB = headB;int countA = 0, countB = 0;while (tailA->next)//既通过找到尾结点判断两个链表的尾结点是否相等//来判断是否相交，也能算出长度，为后续磨平长度差做铺。{tailA = tailA->next;countA++;}while (tailB->next){tailB = tailB->next;countB++;}if (tailA != tailB){return NULL;}else{int n = abs(countA - countB);//无论差值正负,abs都变成正数差值struct ListNode* longList = headA, *shortList = headB;if (countA < countB){longList = headB, shortList = headA;}while (n--)//循环n次，while(--n)循环（n - 1）次{longList = longList->next;}while (longList != shortList){longList = longList->next;shortList = shortList->next;}return longList;}
}