链表的一些算法

求一个单链表的中间节点

思路：快慢指针法，定义一个快指针，每次走两步，慢指针一次走一步，快指针指向结尾时，慢指针指向中间节点

    //求解方法，需要定义一个单链表、添加元素方法，
    //在链表个数为偶数时，返回中间两个节点的后一个节点，并且默认该链表无环
    public Node middleNode(){
        Node fast=headNode;//快指针
        Node slow=headNode;//慢指针
        if(headNode.next==null){
            return null;
        }//处理空链表
        while (fast.next!=null && fast.next.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow.next;
    }

		//测试
        SingleLinkedList singleLinkedList = new SingleLinkedList();
        singleLinkedList.addDate(new Node(1,"wang"));
        singleLinkedList.addDate(new Node(2,"wang1"));
        singleLinkedList.addDate(new Node(3,"wang11"));
        singleLinkedList.addDate(new Node(4,"wang112"));
        singleLinkedList.addDate(new Node(5,"wang1123"));
        Node middleNode = singleLinkedList.middleNode();
        if(middleNode==null){
            System.out.println("该链表为空");
        }else {
            System.out.println("该链表的中间节点为："+middleNode.toString());
        }

检查单链表是否有环

	//需要设置一个创建有环和无环链表的方法用于测试，该方法返回链表的头节点
    public void isRing(Node node){
        Node fast=node.next;//快指针
        Node slow=node;//慢指针
        if(node.next==null){
            System.out.println("链表为空，无环");
            return;
        }else if(node.next.next==null||node.next.next.next==null){
            System.out.println("链表元素为一个或两个，无环");
            return;
        }
        while (true){
            if(fast==null||fast.next==null){
                System.out.println("无环");
                return;
            }
            if(fast==slow){
                System.out.println("有环");
                return;
            }else {
                fast=fast.next.next;
                slow=slow.next;
            }
        }
    }

3链表反转

	//反转方法，三指针法，定义三个指针，分别指向前一个节点、当前节点、后一个节点，将当前节点指向前一个节点，然后后移三个指针，依次循环
    public void reverse(){
        if(headNode.next==null){
            System.out.println("链表为空");
            return;
        }
        Node preNode=null;//前一个节点
        Node curNode=headNode.next;//当前节点
        while (curNode != null){
            Node nextNode = curNode.next; // 保存下一个节点
            curNode.next = preNode;       // 反转当前节点的指针
            preNode = curNode;            // 移动preNode
            curNode = nextNode;           // 移动curNode
        }
        headNode.next = preNode;
    }