扣初级算法-22-链表-环形链表

学习目标：

本次学习目标为 力扣初级算法-链表，其中主要的LC如下：

• 环形链表

学习内容：

解题思路：

• 解法一： 快慢指针

• 边界问题：入参是一个空的

• 代码逻辑过程:

  • 声明快慢指针节点
  • 循环遍历链表，但是快节点 每次跳跃两个节点，此处的循环条件应该是 null != fastNode.next ，因为 需要跳跃两个next，如果无第一个 next 判断，胡直接空指针
  • 当遍历到两个节点 一致时，即可知道当前链表是环形
  • 原理是 在一个环形中，只要快、慢指针的速度不一致，那么他们一定会相遇。

• 代码实现：

	/**
	 * 解法一： 快慢指针
	 */
	public boolean hasCycle01(ListNode head) {
		// 边界问题： 入参是一个空的
		if (null == head) {
			return false;
		}
		// 声明快慢指针节点
		ListNode fastNode = head;
		ListNode slowNode = head;

		// 循环遍历链表，但是快节点 每次跳跃两个节点，此处的循环条件应该是  null != fastNode.next ，因为 需要跳跃两个next，如果无第一个 next 判断，胡直接空指针
		while (null != fastNode && null != fastNode.next) {
			slowNode = slowNode.next;
			fastNode = fastNode.next.next;
			// 当遍历到两个节点 一致时，即可知道当前链表是环形
			if (slowNode == fastNode) {
				return true;
			}
		}
		return false;

	}

• 解法二： 使用 Set 集合 数据结构来判断

• 边界问题：入参是一个空的

• 代码逻辑过程:

  • 声明Set 集合承载 链表的节点
  • while 循环，当循环到节点已存在 Set 集合，则表明当前链表是一个环形

• 代码实现：

	/**
	 * 解法二： 使用 Set 集合 数据结构来判断
	 */
	public boolean hasCycle02(ListNode head) {
		Set<ListNode> set = new HashSet<>();
		while (null != head) {
			if (set.contains(head)) {
				return true;
			}
			set.add(head);
			head = head.next;
		}
		return false;
	}

• 解法三： 删除法

• 边界问题：入参是一个空的

• 解法原理：

  • 通过在删除节点的时候，将节点 node 的 next 指向 node 自己，当后面节点判断 next 是否为 node 自己，即可知道自己是否已删除过

• 代码逻辑过程:

  • 当 head 的next 是他自己时，表明当前节点已经被 自己删除过
  • 将 head 指向 head 的 next ，并递归下一个链表节点

• 代码实现：

	/**
	 * 解法二： 删除法
	 *
	 */
	public boolean hasCycle03(ListNode head) {

		// 边界问题 ： 入参的链表长度为 0
		if (null == head || null == head.next) {
			return false;
		}

		// 解法原理： 通过在删除节点的时候，将节点 node 的 next 指向 node 自己，当后面节点判断 next 是否为 node 自己，即可知道自己是否已删除过

		// 当 head 的next 是他自己时，表明当前节点已经被 自己删除过
		if (head.next == head) {
			return true;
		}

		ListNode listNode = head.next;
		head.next = head;

		return hasCycle03(listNode);

	}