Java实现单链表，反转链表，检测是否成环

素颜马尾好姑娘i 2024-03-17 21:01 92阅读 0赞

class ListNode {
        int val;
        ListNode next;
        
        public ListNode(int val) {
            this.val = val;
            this.next = null;
        }
    }
    
    class LinkedList {
        ListNode head;
        
        public LinkedList() {
            this.head = null;
        }
        
        // 向链表末尾添加节点
        public void addNode(int val) {
            ListNode newNode = new ListNode(val);
            
            if (head == null) {
                head = newNode;
            } else {
                ListNode current = head;
                while (current.next != null) {
                    current = current.next;
                }
                current.next = newNode;
            }
        }
        
        // 反转链表
        public void reverseList() {
            ListNode prev = null;
            ListNode current = head;
            
            while (current != null) {
                ListNode nextNode = current.next;
                current.next = prev;
                prev = current;
                current = nextNode;
            }
            
            head = prev;
        }
        
        // 检测链表是否成环
        public boolean hasCycle() {
            if (head == null)
                return false;
            
            ListNode slow = head;
            ListNode fast = head.next;
            
            while (fast != null && fast.next != null) {
                if (slow == fast)
                    return true;
                
                slow = slow.next;
                fast = fast.next.next;
            }
            
            return false;
        }
    }

测试用例

public class Main {
        public static void main(String[] args) {
            LinkedList linkedList = new LinkedList();
            linkedList.addNode(1);
            linkedList.addNode(2);
            linkedList.addNode(3);
            
            // 反转链表
            linkedList.reverseList();
            
            // 检测链表是否成环
            System.out.println(linkedList.hasCycle());
        }
    }