目录
- 题目
- 1- 思路
- 2- 实现
- ⭐141. 环形链表——题解思路
- 3- ACM实现
题目
- 原题连接:141. 环形链表
1- 思路
模式识别
- 模式1:判断链表的环 ——> 快慢指针
思路
- 快指针 ——> 走两步
- 慢指针 ——> 走一步
- 判断环:若快慢相遇则有环,若到终止条件
fast.next == null || fast.next.next == null
没有相遇返回false
2- 实现
⭐141. 环形链表——题解思路
public class Solution {public boolean hasCycle(ListNode head) {// 快慢指针ListNode slow = head;ListNode fast = head;while(fast!=null && fast.next!=null){slow = slow.next;fast = fast.next.next;if(slow==fast){return true;}}return false;}
}
3- ACM实现
public class isCycle {static class ListNode{int val;ListNode next;ListNode(){}ListNode(int x){val = x;}}public static boolean isCycle(ListNode head){// 快慢指针ListNode slow = head;ListNode fast = head;while(fast!=null && fast.next!=null){slow = slow.next;fast = fast.next.next;if(slow == fast){return true;}}return false;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("输入链表长度");int n = sc.nextInt();ListNode head = null,tail = null;System.out.println("输入链表");for(int i = 0 ; i < n;i++){ListNode newNode = new ListNode(sc.nextInt());if(head==null){head = newNode;tail = newNode;}else{tail.next = newNode;tail = newNode;}}System.out.println("输入环的位置(第几个元素)");int index = sc.nextInt();ListNode cur = head;for(int i = 1 ; i < index;i++){cur = cur.next;}tail.next = cur;System.out.println("链表是否有环"+isCycle(head));}
}