重生之“我打数据结构，真的假的？”--2.单链表（完结）

1.链表的深拷贝

. - 力扣（LeetCode）

思路：

1.遍历原链表根据结点保存的数据，申请并复制到新的结点，并且插入到该节点后。

 2.新结点的随机指向结点 = 原链表结点的随机指向结点的下一个结点！！

3.所有malloc的新节点全部连接起来

struct Node* copyRandomList(struct Node* head) {
    struct Node* phead = NULL;
    struct Node* flag = head;
    struct Node* q = NULL;
    struct Node* p = NULL;
    if(head==NULL)
    return q;
    while (flag) {
        q = NULL;
        q = (struct Node*)malloc(sizeof(struct Node));
        q->next = flag->next;
        flag->next = q;
        q->val = flag->val;
        flag = q->next;
    }
    flag = head;
    p = flag->next;
    phead = p;
    while (p->next) {
        if (flag->random == NULL)
            p->random = NULL;
        else {
            p->random = flag->random->next;
        }
        flag = p->next;
        p = flag->next;
    }
     if (flag->random == NULL)
            p->random = NULL;
        else {
            p->random = flag->random->next;
        }
    p=head->next;
     while (p->next)
     {
        p->next=p->next->next;
        p=p->next;
     }
    return phead;
}

2.环形链表|| 

. - 力扣（LeetCode）

思路

1.先判断是否有环

设快指针（一次走两步），慢指针（一次走一步）

若二者相遇则有环，若快指针走到NULL；则无环

2.标记快慢指针相遇处，为p

设q为头；！！！！！！！

在p与q相遇前 p=p->next;q=q->next;

3. p，q相遇时p为入口处；

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode * p=head;
    struct ListNode * q=head;
    if(p==NULL||p->next==NULL) //判断是否有环
    return NULL;
    do
    {
    p=p->next;
    q=q->next->next;
    if(q==NULL||q->next==NULL)
    return NULL;
    }while(p!=q);//判断是否有环
    p=head;
    while(p!=q)
    {
        p=p->next;
        q=q->next;
    }
    return p;
    
}

3.错题反思

. - 力扣（LeetCode）

原思路：

1.实在想不到什么好办法；如果从a链表首节点开始，每次遍历一遍b表找第一个相同节点太耗费时间，意义不大。

2.也想过建立两个栈，让a，b各节点进栈，根据栈的后进先出从尾出栈开始比。

答案思路（nb！！！）

1. 如果两链表有共同节点

设a表头到共同节点的距离为x；

b表头到共同节点的距离为y；

共同节点到NULL的距离为n；

2.while（a！=b）

遍历a，b链表；

当a为NULL,a=headb;

当b为NULL,b=heada;

3.a与b必然在共同节点处相遇

因为a走的距离为：x+n+y；

b走的距离为：y+n+x；

4.

以a为例：

a走完x+n步后，变为headb，再走y步正好为共同节点处

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *A = headA;
    struct ListNode *B = headB;
    while (A != B) {
        A = A ? A->next : headB;
        B = B ? B->next : headA;
    }
    return A;
}