目录
- 一、相交链表
- 二、环形链表1
- 三、环形链表2
- 四、链表分割
- 五、复制带随机指针的链表
一、相交链表
题目：
示例：
注意：不能根据节点的值来比较是否相交，而是根据节点在内存中是否指向相同的位置。
例如以上图：
链表A：4、1、8、4、5
链表B：5、6、1、8、4、5
链表A和链表B都有节点的值为1，但是它们在内存中指向不同的位置，而值为8的节点（A的第三个节点、B的第四个节点）则在内存中指向相同的位置。
大体思路：链表A和链表B如果相交，那么它们的后几个或者一个节点的位置是一样的。它们的长度不一定一样长，所以要先计算出链表A和链表B的长度，让较长的链表先走长度差的距离，然后再同时走，直到两个链表相交，返回那个开始相交的节点。
计算链表长度：
分别定义一个变量遍历链表，不为空计数器加1往后走，直到循环结束跳出。
如果没有相交返回空：
此时分别遍历两个链表的指针已经走到尾了。假设两个链表有相交，不管是一个还是多个，那么这两个指针肯定是一样的（指相交）；如果两个链表不相交，即使是最后的节点也同样不相交，所以就直接返回NULL。
较长的链表先走节点数之差：
用一个变量等于链表长度之差，因为并不知道是A链表长还是B链表长，所以使用绝对值函数abs。先假设是A链表长，B链表短。设置一个条件，如果A链表的长度小于B链表的长度，就反过来。如果假设的是对的，较长的链表先走长度之差的距离。
一起走，直到相交：
两个链表同时走到某个节点相交了，就跳出循环，然后赋给新的头指针，并且返回这个头指针。
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
int len1=0;
int len2=0;
struct ListNode *cur1=headA;
struct ListNode *cur2=headB;
//先算出两个链表的节点数
while(cur1)
{
len1++;
cur1=cur1->next;
}
while(cur2)
{
len2++;
cur2=cur2->next;
}
//如果没有相加点返回空
if(cur1!=cur2)
{
return NULL;
}
//长的先走节点数之差
int k=abs(len1-len2);
struct ListNode *longhead=headA;
struct ListNode *shorthead=headB;
if(len1<len2)
{
longhead=headB;
shorthead=headA;
}
while(k)
{
longhead=longhead->next;
k--;
}
//一起走，直到相交
while(longhead!=shorthead)
{
longhead=longhead->next;
shorthead=shorthead->next;
}
struct ListNode *newhead=longhead;
return newhead;
}
二、环形链表1
题目：
使用的是双指针法
定义两个快慢指针fast和slow，从起点出发。先fast一次走两步，slow一次走一步，再判断两个指针是否相同。如果链表有环，那么fast或者fast->next永远不为空，一直在循环里转；如果链表没有环，fast又走得比slow快，所以fast或者fast->next到空就结束。这里fast比slow快一步，即每次距离缩短1步，所以只要有环，fast先在环里转，然后slow随后进环，每次它们的距离缩短1，最终相遇。
bool hasCycle(struct ListNode *head) {
struct ListNode *slow=head;
struct ListNode *fast=head;
while(fast&&fast->next)
{
slow=slow->next;
fast=fast->next->next;
if(slow==fast)
{
return true;
}
}
return false;
}
三、环形链表2
题目：
这题与上面的题多增加了一个设定，如果有环，返回的是开始入环的第一个节点。没有环返回空。
那么始入环的第一个节点怎么找呢？其实这里是有关数学计算的。
还是使用两个快慢指针，fast一次走两步，slow一次走一步。如果链表没有环，fast或者fast->next为空，然后返回空指针。如果链表有环，在环的某个位置相遇（注意：fast先入环，可能已经在环里转了n圈了）。假设相遇点与入环点的距离为x，起始点到入环点的距离为L，环的剩下的距离为nC-x（n表示fast已经在环里转了n圈）。
fast从起始点到相遇点的距离为：L+nC+x
slow从起始点到相遇点的距离为：L+x
因为fast一次的步长为slow的两倍
所以：
2（L+x）=L+nC+x
L+x=nC
L=nC-x
根据数学计算转换为：两个指针分别一个从相遇点走，另一个从起始点走，以相同的步长，它们会在入环的第一个节点相遇，然后返回这个相遇点就是入环的第一个节点。
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *slow=head;
struct ListNode *fast=head;
while(fast&&fast->next)
{
fast=fast->next->next;
slow=slow->next;
if(slow==fast)
{
struct ListNode *rid=slow;
struct ListNode *mrid=head;
while(rid!=mrid)
{
rid=rid->next;
mrid=mrid->next;
}
return rid;
}
}
return NULL;
}
四、链表分割
题目：
假设一个链表为：
2、3、1、4、2、5
假设x等于3，数据小于的3的节点有：2、1、2
大于等于3的节点有：3、4、5
题目要求将小于x的节点排在其余节点之前，并且不能改变原来的数据顺序。
大体思路：这里我们可以采用分为两个链表的方式。将数据小于x的节点放在一个A链表里，大于等于的放在B链表里。然后把A链表的尾节点与B链表的头节点连接起来。
但是这里要注意一个问题，如果A链表没有节点怎么与B链表连接，这种情况要单独判断，比较麻烦。所以我们可以采用创建哨兵位头节点解决这个问题。
注意：最后B链表的尾节点要指向空指针，同时释放两个哨兵位节点，返回第一个有效节点。
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
struct ListNode* cur=pHead;
struct ListNode* head1, *tail1, *head2, *tail2;
head1=tail1=(struct ListNode*)malloc(sizeof(struct ListNode));
head2=tail2=(struct ListNode*)malloc(sizeof(struct ListNode));
while(cur)
{
if(cur->val<x)
{
tail1->next=cur;
tail1=tail1->next;
}
else
{
tail2->next=cur;
tail2=tail2->next;
}
cur=cur->next;
}
tail2->next=NULL;
tail1->next=head2->next;
struct ListNode* newhead=head1->next;
free(head1);
free(head2);
return newhead;
}
};
五、复制带随机指针的链表
题目：
要拷贝原节点，并且拷贝节点的随机指针也要指向对应的节点，最后还原原链表。
每个拷贝节点都在原节点的后面：
用一个变量cur遍历链表，只要不为空每次进入循环先定义一个变量next记录原链表的下一个位置（cur在原链表的下一个位置，方便一次拷贝完找到），然后开辟一块空间copy为拷贝节点，把原节点的值赋给拷贝节点，再让cur的下一个地址为copy，copy连接next。
置每个拷贝random：
原链表的每个节点的random指针都有对应的指向，拷贝节点也要有random指针对应的指向，只是拷贝节点的random指针要与原节点的random指针指向保持一致。比如原节点13的random指针指向原节点的7，那么拷贝节点13的random指针则指向拷贝节点的7。
问题是拷贝节点的random指针怎么找到它对应的节点呢？其实上面一步把每个拷贝节点放在原节点的后面有一个好处，方便这一步找到它的random指针。
以拷贝节点13为例：拷贝节点13的random指针，就是它的原节点的random指针所指向的原节点的下一个节点。如果原节点的random指向空，拷贝节点的randon也是指向空。
拷贝节点解下来，尾插在一起，恢复原链表：
struct Node* copyRandomList(struct Node* head) {
struct Node* cur=head;
//复制某个节点到原节点的后面
while(cur)
{
struct Node* next=cur->next;
struct Node* copy=(struct Node*)malloc(sizeof(struct Node));
copy->val=cur->val;
cur->next=copy;
copy->next=next;
cur=next;
}
cur=head;
//处理拷贝节点的random指针指向
while(cur)
{
struct Node* copy=cur->next;
if(cur->random==NULL)
{
copy->random=NULL;
}
else
{
copy->random=cur->random->next;
}
cur=copy->next;
}
cur=head;
//把拷贝指针连接起来，还原原来的链表
struct Node* newhead=NULL;
struct Node* tail=NULL;
while(cur)
{
struct Node* copy=cur->next;
struct Node* next=copy->next;
if(tail==NULL)
{
newhead=tail=copy;
}
else
{
tail->next=copy;
tail=tail->next;
}
cur->next=next;
cur=next;
}
return newhead;
}
感谢观看~
