C语言：环形链表

1.例子1：环形链表

142. 环形链表 II - 力扣（LeetCode）

思路：我们先定义两个变量slow和fast，slow每次走一步，fast每次走两步，如果链表是环形链表，那么必定存在fast不会走到链表的最后并且fast先slow进环，fast和slow一定会在环内相遇。

fast和slow在环内相遇点定义一个指针变量meet，假设圆的周长为C,head从头开始走，meet从相遇点开始走，head点到进环点距离为L，假设slow和fast在圆内的相遇点距离为N,如下图所示：

 

 从上图可知haed和meet必定会相遇，相遇点就是进环点

 代码：

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode* slow = head;struct ListNode* fast = head;while(fast && fast->next){slow = slow->next;fast = fast->next->next;if(slow == fast){struct ListNode* meet=slow;while(meet != head){meet = meet->next;head = head->next;} return meet;}}return NULL;
}

例子2：随机链表的赋值 

 138. 随机链表的复制 - 力扣（LeetCode）

思路：先在每一个节点后面开辟一个拷贝节点copy，拷贝节点的next指针就是cur的next指针，cur的next指针指向拷贝节点，原链表的random指向的下一个节点就是拷贝节点copy的random指向的节点，然后将拷贝节点尾插在一个新链表中，需要注意在尾插在新链表前先将原链表的cur指针重新指向head节点。

 

 

 代码：

struct Node* copyRandomList(struct Node* head) 
{struct Node* cur = head;//开辟新节点copy节点连接在每一个原链表节点的后面while(cur){//开辟copy节点struct Node* copy = (struct Node*)malloc(sizeof(struct Node));copy->val = cur->val;copy->next = cur->next;cur->next = copy;//cur 移动到copy节点的后面节点的位置cur = copy->next;}cur = head;while(cur){struct Node* copy = cur->next;if(cur->random == NULL){copy->random = NULL;}else{copy->random = cur->random->next;}cur= copy->next;}//将copy节点拿下来尾插到新链表中cur = head;struct Node* newhead = NULL,*newtail = NULL;while(cur){//创建新节点copy节点struct Node* copy = cur->next;//是否为空链表，如果是空链表那么新链表的头结点和尾节点都是copy节点if(newtail == NULL){newhead = newtail = copy;}else{newtail->next = copy;newtail = newtail->next;}cur = copy->next;}return newhead;}

 解析：

在原链表中定义一个cur指针指向头结点，使用malloc开辟copy节点，当cur指针不为空时进入while循环，拷贝节点的值为cur的值，即copy->val = cur->val; copy节点的下一个节点指向cur的下一个节点，而cur节点的下一个节点更改为copy节点，即 copy->next = cur->next：cur->next =copy;

cur移动到copy节点的下一个节点，即cur = copy->next;

cur指针重新指向头结点head节点，当cur不为空时进入循环，如果cur的random指向的节点为空，那么copy节点的random节点也为空，如果cur的random指向的节点不为空，那么copy节点的random指向的下一个节点就是copy节点random，即copy->random = cur->random->next;

 cur指针重新指向头结点head节点，定义新链表的头结点和尾节点，当cur不为空时进入循环，如果新链表为空，那么新链表的头结点和尾节点就是copy节点，如果不为空，那么就将copy节点尾插在新链表的后面