2025年- G22-Lc96-链表的中间-java版（false）

1.题目描述

2.思路

方法一：
快慢指针可以判断链表是否有环，也可以判断寻找链表中点。
使用快慢指针，慢指针（slow）：每次移动 1 步；快指针（fast）：每次移动 2 步，当 fast 到达链表末尾时，slow 正好位于中间。
慢指针（slow）：每次移动 1 步，快指针（fast）：每次移动 2 步。当 fast 到达链表末尾时，slow 正好位于中间。
时间复杂度：O(n)，空间复杂度：O(1)。

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}

public class LinkedListCycle {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false; // 为空或只有一个节点，不可能有环
        }

        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;  // fast 遇到 null，说明没有环
    }
}

方法二：
使用arraylist排序，list.get(index)获取对应的索引元素。list.size()/2,计算中间索引。

3.代码实现

方法一：（快慢指针 ）

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {

        ListNode fast=head;
        ListNode slow=head;

        //节点不为空或者只有一个节点
        while(fast!=null&&fast.next!=null)
        {
          slow=slow.next;
          fast=fast.next.next;
        }
        return slow;// 当快指针到达链表末尾，慢指针在中间节点


        // ArrayList<ListNode> list=new ArrayList();
        // ListNode curr=head;
        // while(curr!=null)//当前指针部位null
        // {
        //     list.add(curr);
        //     curr=curr.next;
        // }
        // return list.get(list.size()/2);
        
    }
}

方法二：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode middleNode(ListNode head) {

        // int cnt=0;
        // ListNode current=head;
        // while cu
        ArrayList<ListNode> list=new ArrayList();
        ListNode curr=head;
        while(curr!=null)//当前指针部位null
        {
            list.add(curr);
            curr=curr.next;
        }
        return list.get(list.size()/2);


        
    }
}