[C++知识库]环形指针(双(快、慢)指针)-C语言

环形指针Ⅰ(双(快、慢)指针)

#include <stdio.h>
#include <stdbool.h>
typedef struct ListNode
{
	int data;
	struct ListNode *next;
}Node;

void createList(Node **head, int *arr, int n);
bool hasCycle(Node *head);
void simRing(Node *head);

int main()
{
	Node *head = NULL;
	int arr[6] = {45, 12, 56, 78, 68, 66};
	createList(&head, arr, 6);
	simRing(head);
	printf("%d", hasCycle(head));

}
void createList(Node **head, int *arr, int n)
{
	Node *tail = NULL;
	for(int i = 0; i < n; i++)
	{
		Node *tmp = (Node *)malloc(sizeof(Node));
		tmp->next = NULL;
		tmp->data = arr[i];
		if(*head == NULL)
			*head = tmp;
		else
			tail->next = tmp;
		tail = tmp;
	}
}
//判断是否存在环形指针LeetCode-141
//利用快慢指针来做，如果链表有环，那么slow和fast一定会相遇。
bool hasCycle(Node *head)
{
    struct ListNode *slow = head;
    struct ListNode *fast = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            return true;
    }
    return false;
}

//模拟增加环形
void simRing(Node *head)
{
	Node *tmp = head;
	while(tmp->next)
	{
		tmp = tmp->next;
	}
	tmp->next = head->next;
}

环形指针Ⅱ(双(快、慢)指针)

#include <stdio.h>
#include <stdbool.h>
typedef struct ListNode
{
	int data;
	struct ListNode *next;
}Node;

void createList(Node **head, int *arr, int n);
struct ListNode *detectCycle(struct ListNode *head);
void simRing(Node *head, int n);
int index(Node *head, Node *tmp);

int main()
{
	Node *head = NULL;
	int arr[6] = {45, 12, 56, 78, 68, 66};
	createList(&head, arr, 6);
	simRing(head, 3);
	Node *tmp = detectCycle(head);
	printf("索引值：%d", index(head, tmp));
}
void createList(Node **head, int *arr, int n)
{
	Node *tail = NULL;
	for(int i = 0; i < n; i++)
	{
		Node *tmp = (Node *)malloc(sizeof(Node));
		tmp->next = NULL;
		tmp->data = arr[i];
		if(*head == NULL)
			*head = tmp;
		else
			tail->next = tmp;
		tail = tmp;
	}
}
//判断是否存在环形指针
//利用快慢指针来做，如果链表有环，那么slow和fast一定会相遇。
//开始、入口、相遇   开始-入口 = 入口-相遇
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)
            break;
    }
    if(!fast || !fast->next)
        return NULL;
    slow = head;
    while(slow != fast)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}

//模拟增加环形
void simRing(Node *head, int n)
{
	Node *tmp = head;
	while(tmp->next)
	{
		tmp = tmp->next;
	}
	Node *mmp = head;
	while(n--)
	{
		mmp = mmp->next;
	}
	tmp->next = mmp;
}

//取索引值
int index(Node *head, Node *tmp)
{
	int ind = 0;
	while(head != tmp)
	{
		ind++;
		head = head->next;
	}
	return ind;
}