141.环形链表

题目描述

题目链接

快慢双指针法实现

#pragma once
#include <iostream>

using namespace std;




typedef struct ListNode
{
	int val;
	struct ListNode* next;
}ListNode,*LinkList;


//头插法创建单链表
void CreateList_H(LinkList& L, int n)
{
	//创建带头结点的单链表 并初始化
	L = new ListNode;
	L->next = NULL;

	//创建新的结点
	ListNode* p;
	for (int i = n-1; i >=0; i--)
	{
		p = new ListNode;
		cout << "请输入第"<<i+1<<"个数据: ";
		cin >> p->val;
		p->next = L->next;
		L->next = p;
	}

}
//打印
void show(LinkList L)
{
	//创建一个结点 并指向L的首元结点
	ListNode* p;
	p = L->next;
	//首元结点不为空
	while (p)
	{
		cout << p->val << " ";
		//指向下一个结点
		p = p->next;
	}
	cout << endl;

}

void Circular_l(LinkList& L)
{

	ListNode* q = L;
	while (q->next!=NULL)
	{
		q = q->next; 
	}

	q->next = L->next->next;
	

}


//快慢双指针
class Solution 
{
public:
	bool hasCycle(ListNode* head) 
	{
		if (!head || !head->next)
		{
			return false;
		}

		ListNode* slow = head;;
		ListNode* fast = head->next;

		while (slow != fast)
		{
			if (!fast || !fast->next)
			{
				return false;
			}
			else
			{
				slow = slow->next;//慢指针移动一步
				fast = fast->next->next;//快指针移动两步
			}
		}
		return true;
	}
};


int main()
{

	LinkList L;
	CreateList_H(L, 4);
	cout << "链表L1：" << endl;
	show(L);
	Circular_l(L);

	
	Solution S;
	bool res = S.hasCycle(L->next);
	if (res)
	{
		cout << "环形链表！" << endl;
	}
	else
	{
		cout << "不是环形链表！" << endl;
	}

	
	system("pause");
	return 0;
}

运行结果

提交结果