【CT】LeetCode手撕—141. 环形链表

题目

• 原题连接：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));
    }
}