题目力扣138题：复制带随机指针的链表
题目：给你一个长度为 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 作为传入参数。
要复制的链表示例：
对于这道题我们要解决的难题就是我们要怎么去给random指针赋值，因为我们如果使用一般的复制方法那么有可能在前面的节点处random可能就指向了后面的节点，这就会让我们的代码出现问题。
这道题的其中一种思路使用的是哈希表但是我暂时还没有学习到哈希表所以就不再这里使用这种方法了。
我是用的是另外一种思路：假设这里有一个链表a->b->c我们就先将每一个节点都复制然后插入到原链表里面变成a->a'->b->b'->c->c';然后我们再将复制链表的random赋值，最后我们将原链表和复制链表分离开返回复制链表的头即可。
思维理解图：
代码实现：
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *next;
* struct Node *random;
* };
*/
struct Node* copyRandomList(struct Node* head)
{
//首先我们要判断这个链表是否为空
if(!head)
return NULL;
struct Node* cur = head;
while(cur)
{
struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));//创建一个新节点
newnode->val = cur->val;
newnode->random = NULL;//这里我们只是复制链表里面的值，但是并不复制random指针
//并将其与原链表链接
newnode->next = cur->next;
cur->next = newnode;
cur = cur->next->next;//这里cur的next指针已经指向了复制节点所以要前进两步才会
//让cur进入原链表的下一个
}//这个循环也就完成了原链表的每一个节点的复制并且将其和原链表链接起来
cur = head;//让cur重新指向头节点
//下面我们就要开始为复制节点的random赋值了
//因为现在的复制链表也在原链表内部所以不会出现指向问题
while(cur)
{
if(cur->random)//如果原链表某个节点的random不为空那么我们就要为这个
//节点的复制节点的random赋值
{
cur->next->random = cur->random->next;
}
cur=cur->next->next;//因为一个next只是让cur去到复制节点而已
}
//完成random之后我们就来到了最后一步分离复制链表和原链表
struct Node* newhead = head->next;//这是我们最后要返回的复制节点的头节点
cur = head;
while(cur)
{
struct Node* p2 = cur->next;
cur->next = p2->next;//这里的p2是复制节点复制节点指向的自然是原链表的下一个节点
if(p2->next)
p2->next = cur->next->next;//这里的cur->next已经被修改了这里的cur->next指向的是原链表的第二个
//节点而这个原链表的第二个节点的下一个节点自然就是复制链表的第二个节点
cur = cur->next;//为下一次分离做准备
//这里的判断条件来源就是当复制链表的下一个节点已经指向空了代表这已经到最后了不需要在改变复制链表的next了
}
return newhead;
}关于if判断的来源可以参考下面的这张图，因为p1为空的时候压根不可能就如循环所以我们不用判断p1是否为空
题目二：力扣160题相交链表
题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
对于这道题我们有多种思路其中一种就是暴力求解即将A链里面所有的值和B链比较，如果有相等就返回这个相等的节点
代码：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
struct ListNode* p1 = headA;
struct ListNode* p2 = headB;
while(p1)
{
while(p2)
{
if(p1==p2)
{
return p2;
}
else
{
p2 = p2->next;
}
}
p2 = headB;//这里很重要因为此时的p2已经指向了最后一个节点必须让其重新指向头节点
p1 = p1->next;
}
return NULL;
}方法二：快慢指针
首先我们要判断这两个链有没有相交直接让两个指针都走到最后，判断这最后一个指针是否相等相等则这两个链表相交，然后我们求出两个链表的长度的差值，让指向长链表的节点先走差值步，再让两个指针一起走当两个指针相等时返回的也就是交点节点
代码：
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
//先确定这两个链表是否相交
struct ListNode* curA = headA;
int lenA = 0;
struct ListNode* curB = headB;
int lenB = 0;
while(curA)
{
curA = curA->next;
lenA++;
}
while(curB)
{
curB = curB->next;
lenB++;
}
if(curA!=curB)
return NULL;//证明这两个链表没有节点
struct ListNode* longlist = headA;
struct ListNode* shortlist = headB;
int gbs = abs(lenA-lenB);//算出差值
if(lenB>lenA)
{
longlist = headB;
shortlist = headA;
} //这种写法就能够减少重复代码的使用
while(gbs--)
{
longlist = longlist->next;
}
while(longlist!=shortlist)
{
shortlist = shortlist->next;
longlist = longlist->next;
}
return shortlist;
}