数据结构：单链表OJ题

相交链表

题目描述：

案例：


题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

解题思路

既然要验证链表是不是相交的链表，就必须创建两个指针分别指向两个链表，当遍历时只要由一个节点满足两个指针相等，就说明是相交链表。
这里就要分情况了：

1. 当两个链表长度相同时，让两个指针依次遍历数据直到两个指针相等或者有一个遍历结束置为NULL，相等就相交，反之则不相交。
2. 两个链表长度不同，我们想让他们通过常规遍历肯定是不行了，但是根据第一种情况，我们可以通过一些操作使得两个链表长度相等，也就是两个指针在同一起跑线上，这样就把第二种情况转化成了第一种情况。
   那么怎么让两个指针在同一起跑线上，很简单，遍历两个指针，计数他们的长度，求出长度相差的绝对值n，让长节点的指针先走n步，然后两个链表再同时遍历即可。

代码

/**结构体格式
 * 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* l1=headA;
    ListNode* l2=headB;
    int num1,num2,tmp;//定义链表大小以及绝对值
    num1 =num2 =0;
    //求链表长度
    while(l1)
    {
        num1++;
        l1=l1->next;
    }
    while(l2)
    {
        num2++;
        l2=l2->next;
    }
     //定义长短链表
    ListNode* l=NULL;//长链表
    ListNode* s=NULL;//短链表
    if(num1>num2)
    {
        tmp=num1-num2;
        l=headA;
        s=headB;
    }
    else
    {
        tmp=num2-num1;
        l=headB;
        s=headA;
    }
    //长链表先走n步
    while(tmp--)
    {
        l=l->next;
    }
    //两个链表同时遍历
    while(l&&s)
    {
        if(l==s)
        {
            return l;
        }
        l=l->next;
        s=s->next;
    }
    return NULL;
}

环形链表（I）

题目描述：

案例：

题目链接：https://leetcode.cn/problems/linked-list-cycle/description/

解题思路

这个题目很简单，是比较经典的快慢指针问题。
快慢指针：定义两个指针，一个走得慢，一个走得快。
解题：
定义两个指针，一个快指针一个慢指针，慢指针一次走一步，快指针一次走两步，因为是环形链表，所以不会走到NULL，当碰到NULL停下来说明不是环形链表，但如果是环形链表就变成了类似于操场跑步的情况，快的和慢的终究会相遇，相遇就代表该链表有环。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    ListNode* slow=head;//慢指针
    ListNode* fast=head;//快指针
    while(fast&&fast->next)//快慢指针遍历
    {
    	//这里注意让指针先走在判断，刚开始两个指针都是指向首地址，如果不走直接判断就会导致无论什么情况都是有环的。
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            return true;
        }
    }
    return false;
}

环形链表（II）

题目描述：

案例：

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/

解题思路

先通过快慢指针找到公共节点meet。
让⼀个指针从链表起始位置开始遍历链表,同时让⼀个指针从判环时相遇点（meet）的位置开始绕环运行,两个指针都是每次均⾛⼀步,最终肯定会在入口点的位置相遇。
可能会有人觉得不一定，这个只会在一些特定情况下实现，我们可以来试着证明一下。

注：M为相遇点，E为入环点，环长度为R
要满足上面的结论，就要满足L=R-X
我们可以通过快慢指针之间的关系来证明这个关系式的可靠性（慢指针走一步，快指针走2步）。
慢指针走的路程：L+X
快指针走的路：L+X+nR
既然他们能够相遇，就可以满足2*(L+X)=L+X+nR(快指针走的是慢指针的两倍)
进一步推导：
L+X=nR
L=nR-X
因为这是一个环，所以无论n是多少，他走完一圈就会再次回到原点，所以n在这里对这个关系式就没有影响，由此可得，上述结论是可行的。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
    ListNode* slow,*fast;
    slow=fast=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)//寻找相遇点
        {
            ListNode* meet=fast;//定义相遇点，为了可观性进行了重定义，也可以直接使用fast/slow
            ListNode* pcur=head;
            while(pcur!=meet)//两个指针开始遍历
            {
                pcur=pcur->next;
                meet=meet->next; 
            }
            return meet;
        }
    }
    return NULL;
}

随机链表的复制（深拷贝）

题目描述：

案例：

题目链接：https://leetcode.cn/problems/copy-list-with-random-pointer/description/

解题思路

1. 创建新的链表，并且与原链表产生联系，将新链表的random初始化为NULL
   

2. 修改新链表的random
   分析题目可得，我们复制的链表中随机指针也要对应原链表在新链表中对应的位置。
   定义新链表为copy，观察上图，我们要修改新链表的random，只需要将新链表的random指向原链表指向的random->next。当原链表中random指向NULL，就不需要再做处理，因为我们初始化就是置random为NULL。
   举个例子：以13节点为例
   我们新链表中13节点要指向新链表7节点，7节点的位置再原链表13节点random指向的节点的下一个节点。
   pcur为我们创建的原链表头节点
   即copy->random=pcur->random->next;

   经过分析就可得，我们要创建两个指针分别指向新旧链表得头节点。

3. 断开新旧链表的联系
   我们将原链表头节点走到要修改的新链表后面一个节点的位置，如图：
   
   newhead为新链表头节点地址，newtail为新链表尾节点地址，
   将newtail->next指向pcur->next，
   将newtail向后移一位，pcur一直赋值为newtail的后一位。

代码

/**
 * 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;
}
struct Node* copyRandomList(struct Node* head) {
    if(head==NULL)//当链表为NULL单独处理
    {
        return NULL;
    }
	Node* pcur=head;
    //将新链表与原链表创建联系
    while(pcur)
    {
        Node* newnode=BuyNode(pcur->val);
        newnode->next=pcur->next;
        pcur->next=newnode;
        pcur=newnode->next;
    }
    //修改新链表的random
    pcur=head;
    while(pcur)
    {
        Node* copy=pcur->next;
        if(pcur->random!=NULL)
        {
            copy->random=pcur->random->next;
        }
        pcur=copy->next;
    }
    //将新链表与原链表断开联系
    pcur=head;
    Node* newHead,*newTail;
    newHead=newTail=pcur->next;
    while(pcur->next->next)
    {
        pcur=newTail->next;
        newTail->next=pcur->next;
        newTail=newTail->next;
    }
    return newHead;
}

----------------------------------------------------------------分隔符
西靠：慢指针走一步，快指针走3步、4步、5步…，快慢指针是否会相遇？
答案：一定会相遇。因为篇幅太长，就不做过多解释了。
有兴趣的可以尝试一下，当然也可以记住结论以后使用知道即可。
感谢各位的观看，有错请在评论区指正，谢谢！