【算法】链表常见算法3

【算法】—— 链表常见算法3

1. 相交链表

1.1 问题描述

给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回NULL 。

图示两个链表在节点c1开始相交：

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

1.2 实现思路

​ 首先想到的是暴力求解，但是我们不这样实现，通过遍历链表得到两个链表的长度，判断尾结点是否相等，若是相等则为相交链表，若是不相等则不相交，对于相交链表，让长的链表先走够差值，再让两个链表一起走，相遇的位置就是相交的链表处

1. 分别遍历两个链表，记录出两个链表的长度为7和5，比较两个链表尾结点相等，链表相交

2. 先遍历长的链表，遍历的结点个数是两个链表长度的差

3. 两个链表一起遍历，相遇位置就是相交的链表

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

2. 环形链表I

2.1 问题描述

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
1
2
3

示例 2：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
1
2
3

2.2 实现思路

带环链表不能直接遍历，否则会进入死循环，所以我们使用快慢指针来判断，快指针走两步慢指针走一步，若是链表带环则两个指针总会相遇，若是不带环，则快指针一定先到NULL

n圈之后：快慢指针相遇

为什么快慢指针最后能够相遇？

1. 快指针先进入环中，慢指针再次进入环中，快慢指针之间就会有距离，此时快指针追赶慢指针。
2. 快指针走2步，慢指针走一步，两个指针每走一次它们的距离就会缩小一个，直到完全相遇。

快指针走3步，慢指针走1步，是否也能相遇？

不一定。

1. 快慢指针进入环时的距离为N，快慢指针每走一次它们的差距就会缩小2个。
2. 若是N是奇数，则追赶上时快指针会跨过慢指针，两者距离为-1，快指针相对于慢指针的距离就成了环长减一。
3. 若是环长减一也是偶数，则再追一圈就追上了，若环长减一为奇数，则永远也追不上。

即：N为奇数且环长为偶数时不会相遇

2.3 代码实现

//链表结点声明
struct ListNode 
{
    int val;
    struct ListNode *next;
};
1
2
3
4
5
6

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3. 环形链表II

3.1 问题描述

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

3.2 实现思路

方法一（公式法）

​ 快指针走2步，慢指针走1步

​ 假设入环前的长度为L，环的长度为C，入环点到相遇点的距离为X

1. 因为：slow入环后不可能走过一圈，因为fast和slow的距离不可能超过一圈
   所以：slow走过的距离为：$L+X$

2. 因为：fast入环后不一定只转了一圈，若是L很长，圈很小，slow入环前fast就已经转了很多圈，假设fast在slow入环之前转了n圈（$n>=1$）
   所以：fast走过的距离为：$L+n\times C+X$

3. 因为：快指针走2步，慢指针走一步，即：$fast的距离=2\times slow的距离$
   所以：$2\times (L+X)=L+n\times C+X$
   化简为：$L+X=n\times C$
   化简为：$L=n\times C-X$
   分配律：$L=(n-1)\times C+C-X$
   加括号：$L=[(n-1)\times C]+[C-X]$

1. L的意义是从开始位置到入环点的距离。
2. (n-1)*C的意义是转了$n-1$圈
3. C-X的意义是从相遇点顺时针到入环点的位置

结论：指针A从头开始走，B从相遇点开始走，第一个相遇的位置一定是入环点。

实现步骤：

1. 找到链表的相遇点
2. 定义A、B指针分别从头和相遇点开始出发，相遇的地方即是入环点

代码实现

//链表结点声明
struct ListNode 
{
    int val;
    struct ListNode *next;
};
1
2
3
4
5
6

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

方法二（转换为相交问题）

1. 找到相遇点，将相遇点断开，形成相交的两个链表

2. 分别以相遇点的下一个结点和开始结点作为两个链表的头结点，找链表的交点

3. 还原链表并返回入环点

代码实现

相交链表的函数（在本文第一个算法处实现）

//相交链表函数，返回值为相交结点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB);
1
2

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

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]]
1
2

示例 2：

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]
1
2

示例 3：

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]
1
2

4.2 实现思路

最容易实现的是暴力求解的方法：

1. 复制原链表结点
2. 更新random，遍历链表，找到每个结点的random在原链表中指向第几个结点，然后使新链表的random指向自身的第几个结点
3. 时间复杂度是$O(n^2)$，容易理解但是效率低，我们不实现这种方法

我们使用原地拷贝的方法对如下链表实现深拷贝：

1. 复制每个结点，将其连接在源链表的每个结点的后面

展开为下图：

2. 更新random，通过源结点的random找到复制结点的random指向，源节点的下一个结点就是该节点的复制结点

展开如下图：

3. 将拷贝链表解下来，形成新链表。将新链表返回

代码实现

//链表结点声明
struct Node
{
    int val;
    struct Node *next;
    struct Node *random;
};
1
2
3
4
5
6
7

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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53