四、环形链表
思路1：暴力求解O(N^2)
依次取A链表中的每个节点与B链表中的所有结点相比较，如果有地址相同的结点，就是相交；
思路2：快慢指针法O(N)
1.尾结点相同就是相交，否则就不相交；
2.求交点：长的链表先走（长度差）步，再同时走，第一个相同的就是交点；
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { struct ListNode *slow = head,*fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { return true; } } return false; }
思考两个问题：
①为什么slow和fast一定会在环中相遇？有没有错过的情况，永远遇不上？
②为什么slow走一步，fast一次走两步？可不可以fast一次走N（N>2）步?
-------------------------------------------------------------------------------------------------------------------------
解答：
slow一次走一步，fast一次走两步；一定会相遇
1.slow和fast相比较，fast一定是先进入环的，此时slow走了入环前的一半；
2.随着slow进环，fast已经在环里面走了一段了，走了多和环的大小有关；
slow一次走一步，fast一次走三步；不一定会相遇
如果N是4、5、6......，其推到过程也是一样的；
五、环形链表 II
思路： 快慢指针
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *detectCycle(struct ListNode *head) { struct ListNode* slow = head,*fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { struct ListNode* meet = slow; while(head != meet) { meet = meet->next; head = head->next; } return meet; } } 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 作为传入参数。
链接：https://leetcode-cn.com/problems/copy-list-with-random-pointer
思路：
1.拷贝节点并插入原节点的后面；
2.根据原节点，处理copy节点的random；
3.把拷贝节点解下来，链接成新链表。同时恢复原链表；
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { //1.拷贝节点并插入原节点的后面 struct Node* cur = head; while(cur) { struct Node* copy = (struct Node*)malloc(sizeof(struct Node)); copy->val = cur->val; //插入copy节点 copy->next = cur->next; cur->next = copy; cur = copy->next; } //2.根据原节点，处理copy节点的random cur = head; while(cur) { struct Node* copy = cur->next; if(cur->random == NULL) { copy->random = NULL; } else { copy->random = cur->random->next; } cur = copy->next; } //3.把拷贝节点解下来，链接成新链表。同时恢复原链表； struct Node* copyHead = NULL, *copyTail = NULL; cur = head; while(cur) { struct Node* copy = cur->next; struct Node* next = copy->next; if(copyTail == NULL) { copyHead = copyTail = copy; } else { copyTail->next = copy; copyTail = copy; } cur->next = next; cur = next; } return copyHead; }
以上是链表相关练习的总结；动图如有错误，请联系博主；
