数据结构——链表练习题

题目一：

思路：双指针
当listA和listB其中一个位空时，两个列表就不存在相交，返回NULL；
当listA和listB都不为空链表时，指针phead1和phead2同时分别遍历listA和listB。遍历完后，再去分别遍历listB和listA,相等时为相交节点。

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
    struct ListNode*phead1=headA;
    struct ListNode*phead2=headB;
    if(phead1==NULL||phead2==NULL)
    {
        return NULL;
    }    
    while(phead1!=phead2)
    {
        if(phead1==NULL)
        {
            phead1=headB;
        }
        else
        {
            phead1=phead1->next;
        }
        if(phead2==NULL)
        {
            phead2=headA;
        }
        else
        {
            phead2=phead2->next;
        }
    }
    return phead1;
}

题目二

struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode*slow=head;
    struct ListNode*fast=head;
    //找到相遇的位置
    if(head==NULL)
        return NULL;
    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;
        if(slow==fast)
        {
            slow=head;
            while(slow!=fast)
            {
                slow=slow->next;
                fast=fast->next;
            }
            return slow;
        }
    }
    return NULL;
}

题目三：

bool hasCycle(struct ListNode *head) 
{
    struct ListNode*fast=head;
    struct ListNode*slow=head;    
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            return true;
        }
    }
    return false;
}

题目四：

struct Node* copyRandomList(struct Node* head) {
	struct Node* cur=head;
    //插入被拷贝的链表
    while(cur)
    {
        struct Node*next=cur->next;
        struct Node *newcode=(struct Node*)malloc(sizeof(struct Node));
        newcode->val=cur->val;
        newcode->next=next;
        cur->next=newcode;
        cur=next;   
    }
    cur=head;
    while(cur)
    {
        struct Node*next=cur->next->next;
        struct Node*newcode=cur->next;
        if(cur->random!=NULL)
        {
            newcode->random=cur->random->next;
        }
        else
        {
            newcode->random=NULL;
        }
        cur=next;
    }
    //重新链接拷贝的链表
    struct Node*newhead=NULL;
    struct Node*tail=NULL;
    cur=head;
    while(cur)
    {
        struct Node*newcode=cur->next;
        struct Node*next=newcode->next;
        if(newhead==NULL)
        {
            newhead=tail=newcode;
        }
        else
        {
            tail->next=newcode;
            tail=newcode;
        }
        cur->next=next;
        cur=next;
    }
    return newhead;
}