LeetCode Hot 热题100 算法题 141.环形链表-算法&测试-easy模式

LeetCode Hot 热题100 算法题 141.环形链表-算法&测试-easy模式

给定一个链表，判断链表中是否有环。
你能用O(1)内存解决此问题吗？

package leetcode.easy;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

//141.环形链表
public class Solution141 {
	public static void main(String[] args) {
		ListNode head = new ListNode(1);
		head.next=new ListNode(2);
		head.next.next=new ListNode(3);
		head.next.next.next=head.next;
		
		S141CircularList testCircularList = new S141CircularList();
		System.out.println(testCircularList.isCirList(head));
	}
}

class S141CircularList{
	//法1：hashmap 需要额外空间O(n)
	public boolean circularList(ListNode head) {
		Map<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
		ListNode cur = head;
		int pos=0;//记录节点位置
		while(cur!=null) {
			if (!hashMap.containsKey(cur.val)) {
				hashMap.put(cur.val, pos);
				pos++;
			}else {
				return true;
			}
			cur=cur.next;
		}
		return false;
	}
	
	//使用hashset 需要额外空间O(n)
	public boolean cirList(ListNode head) {
		Set<Integer> seen = new HashSet<Integer>();
		ListNode cur = head;
		while(cur!=null) {
			if (!seen.add(cur.val)) {//若set中不含该元素就添加至set，否则不添加并返回false
				return true;
			}
		}
		return false;
	}
	
	//法2：快慢指针  时间复杂度O(1)
	//1.快指针fast每次移动两步，慢指针slow每次移动一步
	//2.二者从同一节点开始移动，若链表没有环，fast将一直在slow前面，不会相遇
	//3.若链表存在环，则fast先进入环并一直在环内移动，slow进入环后，fast一定会在某个时刻与slow相遇
	//4.故while循环退出条件是fast=slow
	//5.初始位置：slow在head，fast在head.next（否则不会进入while--先判断再执行）
	//或者：使用do-while循环，先执行再判断，fast和slow就都从head开始
	
	public boolean isCirList(ListNode head) {
		ListNode fast = head;
		ListNode slow = head;
		do {
			if (fast==null || fast.next==null) {//对单个节点，若其next没指向自身，则不是环形链表
				return false;
			}
			fast=fast.next.next;
			slow=slow.next;
		}while(fast!=slow);
		//正常结束do-while说明fast==slow，相遇则是环形链表
		return true;
	}
}

参考：
https://leetcode-cn.com/problems/linked-list-cycle/solution/huan-xing-lian-biao-by-leetcode-solution