算法３：程序21-２２

程序２１：拷贝含随机指针的链表

#include<iostream> //拷贝含随机指针的链表
using namespace std;
#include<hash_map>

struct Node
{
    int value;
    Node*next;
    Node*random;
    Node(int val)
    {
        value=val;
        next=NULL;
        random=NULL;
    }
};

Node* copyListWithRand1(Node *head)  //未完成
{
    if(head==NULL)
    {
        return NULL;
    }
}
Node* copyListWithRand2(Node *head)  //额外空间为O(1)
{
    if(head==NULL)
    {
        return NULL;
    }
    Node* cur=head;
    Node*next=NULL;
    while (cur!=NULL)
    {
        next=cur->next;
        cur->next=new Node(cur->value); //在new的同时将值拷了进去
        cur->next->next=next;
        cur=next;
    }
    cur=head;
    Node*copy=NULL;
    while(cur!=NULL)
    {
        copy=cur->next;
        copy->random=cur->random==NULL?NULL:cur->random->next;
        cur=cur->next->next;
    }

    cur=head;
    Node*res=cur->next;
    while(cur!=NULL)
    {
        next=cur->next->next;
        copy=cur->next;
        cur->next=next;
        copy->next=next==NULL?NULL:next->next;
        cur=next;
    }
    return res;

};
int main()
{

    Node *head1 = NULL;
    head1=new Node(1);
    head1->next=new Node(2); //一定要new;用类似于有参构造初始化
    Node*res=copyListWithRand2(head1);
    cout<<res->value<<endl;
    cout<<head1->next->random;

    return 0;
}

程序２２：两个单链表相交的一系列问题

#include<iostream> //两个单链表相交的一系列问题
using namespace std;

struct Node
{
    int value;
    Node *next;
    Node(int val)
    {
        value=val;
        next=NULL;
    } 
};


Node* getLoopNode(Node* head)
{
    if(head==NULL||head->next==NULL||head->next->next==NULL)
    {
        return NULL;
    }
    Node* n1=head->next;
    Node* n2=head->next->next;
    while(n1!=n2)
    {
        if(n1==NULL||n2==NULL)
        {
            return NULL;
        }
        n1=n1->next;
        n2=n2->next->next;
    }
    n2=head;
    while (n1!=n2)
    {
        n1=n1->next;
        n2=n2->next;
    }
    return n1;
}

Node* noLoop(Node* head1,Node* head2)
{
    if(head1==NULL||head2==NULL)
    {
        return NULL;
    }
    int n=0;
    Node* cur1=head1;
    Node* cur2=head2;
    while (cur1!=NULL)
    {
        n++;
        cur1=cur1->next;
    }
    while (cur2!=NULL)
    {
        n--;
        cur2=cur2->next;
    }
    if(cur1!=cur2)
    {
        return NULL;
    }    
    cur1=n>0?head1:head2;
    cur2=cur1==head1?head2:head1;
    n=abs(n);
    while (n!=0)
    {
        cur1=cur1->next;
        n--;
    }
    while (cur1!=cur2)
    {
        cur1=cur1->next;
        cur2=cur2->next;
    }
    return cur1;
}
Node* bothLoop(Node* head1,Node* loop1,Node* head2,Node* loop2)
{
    Node* cur1=NULL;
    Node* cur2=NULL;
    if(loop1==loop2)
    {
        cur1=head1;
        cur2=head2;
        int n=0;
        while (cur1!=loop1)
        {
            n++;
            cur1=cur1->next;
        }
        while (cur2!=loop2)
        {
            n--;
            cur2=cur2->next;
        }
        cur1=n>0?head1:head2;
        cur2=cur1==head1?head2:head1;
        n=abs(n);
        while (n!=0)
        {
            cur1=cur1->next;
            n--;
        }
        while (cur1!=cur2)
        {
            cur1=cur1->next;
            cur2=cur2->next;
        }
        return cur1;      
    }
    else
    {
        cur1=loop1->next;
        while(cur1!=loop1)
        {
            if(cur1==loop2)
            {
                return loop2;
            }
            cur1=cur1->next;
        }
        return NULL;
    }

}

Node* getIntersectNode(Node* head1,Node* head2)
{
    if(head1==NULL||head2==NULL)
    {
        return NULL;
    }
    Node* loop1=getLoopNode(head1);
    Node* loop2=getLoopNode(head2);
    if(loop1==NULL&&loop2==NULL)
    {
        return noLoop(head1,head2);
    }
    if(loop1!=NULL&&loop2!=NULL)
    {
        return bothLoop(head1,loop1,head2,loop2);
    }
    return NULL;
}

int main()
{
    Node *head1=NULL;
    head1=new Node(1);
    Node* cur=new Node(2);
    cout<<cur<<endl;
    head1->next=cur;

    Node* head2=new Node(3);
    head2->next=cur;

    cout<<getIntersectNode(head1,head2);

    return 0;
}