链表OJ题讲解---试金石含金量

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) 
//判断以head为头节点的单链表是否存在环
{
    ListNode* slow=head,*fast=head;
    while(fast && fast->next)//这是快指针，最先到达链表的末尾，当快指针指向为空，就说明没有环
    {
        slow=slow->next;
        fast=fast->next->next;

        if(fast==slow)
        return true；/如果fast==slow，说明链表是有环的
    }
    return false;//当fast都走到空了，还是没有出现fast==slow的情况，说明链表没有环
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 typedef struct ListNode ListNode;
bool hasCycle(struct ListNode *head) {
    ListNode* slow=head,*fast=head;
    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        //相遇
        if(fast==slow)
        {
            ListNode* meet=slow;//定义一个指针meet，此时slow所在的位置是快慢指针在环内的相遇点
            while(meet != head)//head指针从链表的头节点出发，meet从快慢指针在环内的相遇点出发
            {
                meet=meet->next;
                head=head->next;
            }
            return meet;//相遇的节点就是链表环的入口节点
        }
    }
    return NULL;
}

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;
struct Node* copyRandomList(struct Node* head) {
	Node* cur=head;
    //拷贝节点入原节点的后面
    while(cur)
    {
        //为拷贝的节点申请空间
        Node* copy=(Node*)malloc(sizeof(Node));
        copy->val=cur->val;//先复制数值

        copy->next=cur->next;//把拷贝节点copy插入原节点cur的后面
        cur->next=copy;//让拷贝节点的next指向原节点的下一个节点

        cur=copy->next;//让原节点的next指向拷贝节点
    }
    //控制random
    cur=head;//重新开始遍历链表
    while(cur)
    {
        Node* copy=cur->next;//获取cur对应的拷贝节点copy
        if(cur->random==NULL)
        {
            cur->random=NULL;
        }
        else
        {
            copy->random=cur->random->next;//copy的random指向该原节点random所指向的节点对应的拷贝节点，因为原节点的next就是其对应的拷贝节点
        }
        cur=copy->next;//继续向后循环
    }
    //把拷贝节点取下来尾插成为新链表，然后恢复原来的链表（不恢复也可以）
    Node* copyhead=NULL,* copytail=NULL;
    cur=head;//再次遍历
    while(cur)
    {
        Node* copy=cur->next;//获取当前原节点cur对应的拷贝节点copy
        Node* next=copy->next;//用与后期恢复链表和遍历原链表

        if(copytail==NULL)
        {
            copytail=copyhead=copy;
        }
        else{
            copytail->next=copy;//copy的值尾插
            copytail=copytail->next;//向后移动
        }

        cur->next=next;//用于恢复原链表
        cur=next;//将cur继续向后移动
    }

    return copyhead;//返回拷贝链表的头节点
}