【算法】—— 链表常见算法3
1. 相交链表
1.1 问题描述
给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回NULL 。
图示两个链表在节点c1开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
1.2 实现思路
? 首先想到的是暴力求解，但是我们不这样实现，通过遍历链表得到两个链表的长度，判断尾结点是否相等，若是相等则为相交链表，若是不相等则不相交，对于相交链表，让长的链表先走够差值，再让两个链表一起走，相遇的位置就是相交的链表处
- 分别遍历两个链表，记录出两个链表的长度为7和5，比较两个链表尾结点相等，链表相交
- 先遍历长的链表，遍历的结点个数是两个链表长度的差
- 两个链表一起遍历，相遇位置就是相交的链表
1.3 代码实现
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
//判断链表是否有空
if (headA == NULL || headB == NULL)
{
return NULL;
}
//求出两个链表的长度
struct ListNode *curA = headA, *curB = headB;
int lenA = 0;
while (curA->next != NULL)
{
curA = curA->next;
lenA++;
}
int lenB = 0;
while (curB->next != NULL)
{
curB = curB->next;
lenB++;
}
//两个链表的尾结点不相等，则不相交
if (curA != curB)
{
return NULL;
}
//长链表先走长度差步
struct ListNode *longList = headA, *shortList = headB;
if (lenA < lenB)
{
longList = headB;
shortList = headA;
}
int sub = abs(lenA - lenB);
while (sub--)
{
longList = longList->next;
}
//两个链表同时走，直到相遇将结果返回
while (longList != shortList)
{
longList = longList->next;
shortList = shortList->next;
}
return longList;
}
2. 环形链表I
2.1 问题描述
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
2.2 实现思路
带环链表不能直接遍历，否则会进入死循环，所以我们使用快慢指针来判断，快指针走两步慢指针走一步，若是链表带环则两个指针总会相遇，若是不带环，则快指针一定先到NULL
n圈之后：快慢指针相遇
为什么快慢指针最后能够相遇？
- 快指针先进入环中，慢指针再次进入环中，快慢指针之间就会有距离，此时快指针追赶慢指针。
- 快指针走2步，慢指针走一步，两个指针每走一次它们的距离就会缩小一个，直到完全相遇。
快指针走3步，慢指针走1步，是否也能相遇？
不一定。
- 快慢指针进入环时的距离为N，快慢指针每走一次它们的差距就会缩小2个。
- 若是N是奇数，则追赶上时快指针会跨过慢指针，两者距离为-1，快指针相对于慢指针的距离就成了环长减一。
- 若是环长减一也是偶数，则再追一圈就追上了，若环长减一为奇数，则永远也追不上。
即：N为奇数且环长为偶数时不会相遇
2.3 代码实现
//链表结点声明
struct ListNode
{
int val;
struct ListNode *next;
};
bool hasCycle(struct ListNode *head)
{
struct ListNode *first = head, *slow = head;
while (first != NULL && first->next != NULL)
{
first = first->next->next;
slow = slow->next;
if (slow == first)
{
return true;
}
}
return false;
}
3. 环形链表II
3.1 问题描述
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null
3.2 实现思路
方法一（公式法）
? 快指针走2步，慢指针走1步
? 假设入环前的长度为L，环的长度为C，入环点到相遇点的距离为X
因为：
slow入环后不可能走过一圈，因为fast和slow的距离不可能超过一圈
所以：slow走过的距离为： L + X L + X L+X因为：
fast入环后不一定只转了一圈，若是L很长，圈很小，slow入环前fast就已经转了很多圈，假设fast在slow入环之前转了n圈（ n > = 1 n >= 1 n>=1）
所以：fast走过的距离为： L + n × C + X L + n\times C + X L+n×C+X因为：快指针走2步，慢指针走一步，即： f a s t 的距离 = 2 × s l o w 的距离 fast的距离 = 2 \times slow的距离 fast的距离=2×slow的距离
所以： 2 × ( L + X ) = L + n × C + X 2 \times (L + X) = L+n \times C + X 2×(L+X)=L+n×C+X
化简为： L + X = n × C L+X = n \times C L+X=n×C
化简为： L = n × C ? X L = n \times C - X L=n×C?X
分配律： L = ( n ? 1 ) × C + C ? X L = (n-1) \times C + C - X L=(n?1)×C+C?X
加括号： L = [ ( n ? 1 ) × C ] + [ C ? X ] L = [(n-1) \times C] + [C - X] L=[(n?1)×C]+[C?X]
L的意义是从开始位置到入环点的距离。(n-1)*C的意义是转了 n ? 1 n-1 n?1圈C-X的意义是从相遇点顺时针到入环点的位置
结论：指针A从头开始走，B从相遇点开始走，第一个相遇的位置一定是入环点。
实现步骤：
- 找到链表的相遇点
- 定义A、B指针分别从头和相遇点开始出发，相遇的地方即是入环点
代码实现
//链表结点声明
struct ListNode
{
int val;
struct ListNode *next;
};
struct ListNode *detectCycle(struct ListNode *head)
{
//快慢指针寻找相遇点
struct ListNode *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
//找到相遇点时，A、B分别从头和相遇点开始找入环点
if (fast == slow)
{
struct ListNode *A = head, *B = fast;
while (A != B)
{
A = A->next;
B = B->next;
}
return A;
}
}
return NULL;
}
方法二（转换为相交问题）
- 找到相遇点，将相遇点断开，形成相交的两个链表
- 分别以相遇点的下一个结点和开始结点作为两个链表的头结点，找链表的交点
- 还原链表并返回入环点
代码实现
相交链表的函数（在本文第一个算法处实现）
//相交链表函数，返回值为相交结点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB);
struct ListNode *detectCycle(struct ListNode *head)
{
//快慢指针寻找相遇点
struct ListNode *slow = head, *fast = head;
while (fast != NULL && fast->next != NULL)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
{
//断开相遇点
struct ListNode* next = fast->next;
fast->next = NULL;
//调用链表相交函数找到相交点，就是入环点
struct ListNode* meet = getIntersectionNode(head, next);
//还原环形链表，并返回入环点
fast->next = next;
return meet;
}
}
return NULL;
}
4. 复制带随机指针的链表
4.1 问题描述
? 给你一个长度为n的链表，每个节点包含一个额外增加的随机指针random，该指针可以指向链表中的任何节点或空节点。
? 构造这个链表的深拷贝。 深拷贝的链表应与原链表的数据域完全一致，随机指针的指向与原链表的随机指针的指向一一对应，但是不能直到原链表的结点中
示例 1：
输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
示例 3：
输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
4.2 实现思路
最容易实现的是暴力求解的方法：
- 复制原链表结点
- 更新
random，遍历链表，找到每个结点的random在原链表中指向第几个结点，然后使新链表的random指向自身的第几个结点- 时间复杂度是 O ( n 2 ) O(n^2) O(n2)，容易理解但是效率低，我们不实现这种方法
我们使用原地拷贝的方法对如下链表实现深拷贝：
- 复制每个结点，将其连接在源链表的每个结点的后面
展开为下图：
- 更新
random，通过源结点的random找到复制结点的random指向，源节点的下一个结点就是该节点的复制结点
展开如下图：
- 将拷贝链表解下来，形成新链表。将新链表返回
代码实现
//链表结点声明
struct Node
{
int val;
struct Node *next;
struct Node *random;
};
struct Node* copyRandomList(struct Node* head)
{
//链表为空不复制
if (head == NULL)
{
return head;
}
//复制链表结点
struct Node* cur = head;
struct Node* copy = NULL;
while (cur != NULL)
{
copy = (struct Node*)malloc(sizeof(struct Node));
copy->val = cur->val;
copy->next = cur->next;
cur->next = copy;
cur = copy->next;
}
//更新random
cur = head;
while (cur != NULL)
{
copy = cur->next;
if (cur->random != NULL)
{
copy->random = cur->random->next;
}
else
{
copy->random = NULL;
}
cur = copy->next;
}
//解开拷贝链表
struct Node* copyHead = head->next;
cur = head;
while (cur->next->next != NULL) //最后一个结点没有下一个结点的拷贝结点，所以要单独处理
{
copy = cur->next;
//分离拷贝链表
cur->next = copy->next;
copy->next = copy->next->next;
cur = cur->next;
}
cur->next = NULL; //源链表的最后一个结点要置空
return copyHead;
}