单链表算法题进阶篇
相交链表
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。图示两个链表在节点
c1开始相交
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构
- 若两个链表一样长，我们就可以依次比较地址来判断是否有没有相交
- 所以基本思路就是先把两个链表长度计算出来，让两个链表长度对齐
- 然后再逐一比较就可以了
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) { ListNode* p1 = headA; ListNode* p2 = headB; int sizeA, sizeB; sizeA = sizeB = 0; while (p1->next) { sizeA++; p1 = p1->next; } while (p2->next) { sizeB++; p2 = p2->next; } if (p1 == p2) { int size = abs(sizeA - sizeB); if (sizeA < sizeB) { while (size--) { headB = headB->next; } } else { while (size--) { headA = headA->next; } } while (headA) { if (headA == headB) return headA; headA = headA->next; headB = headB->next; } } return NULL; }
环形链表I
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
- 链表存在环的条件是尾节点的next指针不为空
- 快慢指针法
- 即慢指针⼀次⾛⼀步，快指针⼀次⾛两步，两个指针从链表起始位置开始运⾏， 如果链表 带环则⼀定会在环中相遇，否则快指针率先⾛到链表的未尾
证明：
- slow⼀次⾛⼀步，fast⼀次⾛2步，fast先进环，假设slow也⾛完⼊环前的距离，准备进环，此时fast 和slow之间的距离为N，接下来的追逐过程中，每追击⼀次，他们之间的距离缩⼩1步，追击过程中fast和slow之间的距离变化：
- 快指针⼀次⾛3步，⾛4步，…n步⾏吗?
答案是可以
step1:
按照上⾯的分析，慢指针每次⾛⼀步，快指针每次⾛三步，此时快慢指针的最⼤距离为N，接下来的 追逐过程中，每追击⼀次，他们之间的距离缩⼩2步 追击过程中fast和slow之间的距离变化：
分析:
- 如果N是偶数，第⼀轮就追上了
- 如果N是奇数，第⼀轮追不上，快追上，错过了，距离变成-1，即C-1，进⼊新的⼀轮追击
- C-1如果是偶数，那么下⼀轮就追上了
- C-1如果是奇数，那么就永远都追不上
- 总结⼀下追不上的前提条件：N是奇数，C是偶数
Step2：
假设： 环的周⻓为C，头结点到slow结点的⻓度为L，slow⾛⼀步，fast⾛三步，当slow指针⼊环后， slow和fast指针在环中开始进⾏追逐，假设此时fast指针已经绕环x周。
在追逐过程中，快慢指针相遇时所⾛的路径⻓度:
- fast: L+xC+C-N
- slow：L
由于慢指针⾛⼀步，快指针要⾛三步，因此得出： 3 * 慢指针路程 = 快指针路程 ，即：
- 3L = L + xC + C − N
- 2L = (x + 1)C − N
对上述公式继续分析：由于偶数乘以任何数都为偶数，因此 ⼀定为偶数，则可推导出可能得情 况：
- 偶数=偶数
- 奇数-奇数
- 由step1中（1）得出的结论，如果N是偶数，则第⼀圈快慢指针就相遇了。
- 由step1中（2）得出的结论，如果N是奇数，则fast指针和slow指针在第⼀轮的时候套圈了，开始进⾏下⼀轮的追逐；当N是奇数，要满⾜以上的公式，则 (x+1)C 必须也要为奇数，即C为奇数，满⾜ （2）a中的结论，则快慢指针会相遇
因此，step1中的 N是奇数，C是偶数 ，既然不存在该情况，则快指针⼀次⾛3步最终⼀定也 可以相遇。不成⽴
快指针⼀次⾛4、5…步最终也会相遇，其证明⽅式同上
typedef struct ListNode ListNode; bool hasCycle(struct ListNode *head) { ListNode* slow,*fast; slow = fast = head; while(fast && fast->next) { slow = slow->next; int n=3; //fast每次⾛三步 while(n--) { if(fast->next) fast = fast->next; else return false; } if(slow == fast) { return true; } } return false; }
虽然已经证明了快指针不论⾛多少步都可以满⾜在带环链表中相遇，但是在编写代码的时候 会有额外的步骤引⼊，涉及到快慢指针的算法题中通常习惯使⽤慢指针⾛⼀步快指针⾛两步的⽅式。
建议解法
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; bool hasCycle(struct ListNode *head) { ListNode*slow,*fast; slow=fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; if(fast==slow) return true; } return false; }
环形链表II
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。
- 结论:
让⼀个指针从链表起始位置开始遍历链表,同时让⼀个指针从判环时相遇点的位置开始绕环运⾏,两个指针都是每次均⾛⼀步,最终肯定会在⼊⼝点的位置相遇。
证明： 
H为链表的起始点，E为环⼊⼝点，M与判环时候相遇点
设:
环的⻓度为R，H到E的距离为L，E到M的距离为 X ，则：M到E的距离为 R-X
在判环时,快慢指针相遇时所⾛的路径⻓度:
- fast: L+X + nR
- slow：L+X
注意：这里快慢指针是两步和一步
- 当慢指针进⼊环时，二者相遇时快指针可能已经在环中绕了n圈了，n⾄少为1
因为：快指针先进环⾛到M的位置,最后⼜在M的位置与慢指针相遇
2.慢指针进环之后，快指针肯定会在慢指针⾛⼀圈之内追上慢指针
因为：慢指针进环后,快慢指针之间的距离最多就是环的⻓度,⽽两个指针在移动时,每次它们的距离都缩减⼀步，因此在慢指针移动⼀圈之前，快指针肯定是可以追上慢指针的，⽽快指针速度是慢指针的两倍，因此有如下关系是：
- 2 * (L+X)=L+X+nR
- 即：L=nR-X
- 即：L = (n-1)R+(R-X)(n为1,2,3,4…，n的⼤⼩取决于环的⼤⼩，环越⼩n越⼤)
- (n-1)R这一项不影响两个指针的相遇位置，即：⼀个指针从链表起始位置运⾏，⼀个指针从相遇点位置绕环，每次都⾛⼀步，两个指针最终会在⼊⼝点的位置相遇
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ typedef struct ListNode ListNode; ListNode* FindNode(ListNode* head) { ListNode*fast,*slow; slow=fast=head; while(fast&&fast->next) { slow=slow->next; fast=fast->next->next; if(slow==fast) return slow; } return NULL; } struct ListNode *detectCycle(struct ListNode *head) { ListNode* meet=FindNode(head); ListNode*pcur=head; while(meet&&pcur) { if(meet==pcur) return meet; meet=meet->next; pcur=pcur->next; } return NULL; }
随机链表的复制
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的深拷贝。 深拷贝应该正好由 n 个全新节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。
你的代码只接受原链表的头节点 head 作为传入参数。
- 如果是普通链表，我们可以直接按照遍历的顺序创建链表节点。而本题中因为随机指针的存在，当我们拷贝节点时，「当前节点的随机指针指向的节点」可能还没创建，因此我们需要变换思路。
我们在新链表和原链表之间建立联系
- 步骤一：
2.步骤二
3.步骤三
总结
分三步：
- 在原链表基础上复制新的链表
- 改变random指针：copy->random=pcur->random->next
- 将复制链表和原链表断开
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ typedef struct Node Node; Node* BuyNode(int x) { Node* newnode=(Node*)malloc(sizeof(Node)); newnode->val=x; newnode->next=newnode->random=NULL; return newnode; } void AddNode(Node* phead) { Node* pcur=phead; while(pcur) { Node* ret=pcur->next; Node* newnode=BuyNode(pcur->val); pcur->next=newnode; newnode->next=ret; pcur=ret; } } struct Node* copyRandomList(struct Node* head) { if(head==NULL) return NULL; AddNode(head); Node*copy,*pcur,*p1,*newhead,*newtail; pcur=head; newhead=newtail=pcur->next; p1=pcur; while(pcur) { copy=pcur->next; if(pcur->random!=NULL) { copy->random=pcur->random->next; } pcur=copy->next; } while(p1->next->next) { p1=p1->next->next; newtail->next=p1->next; newtail=newtail->next; } return newhead; }
