求链表中环的入口节点

问题描述：一个链表中包含环，如何找到环的入口节点？

解法一：遍历链表中的节点，将节点放入Set集合中，利用Set集合不允许插入重复数据的特性，可以找到第一个重复的节点，即为环的入口　　　　节点。

解法二：定义连个指针p1和p2，p1和p2都指向链表的头结点，p1移动环的个数个节点，然后p1和p2以相同的速度移动，直到p1和p2相遇，相　　　　遇的节点即为环的入口节点。

package com.wyl.linklist;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;

/**
 * 求链表中环的入口节点
 * @author wyl
 *
 */
public class CircleStartNode {

    /**
     * 定义链表中节点的结构
     * @author wyl
     */
    static class Node<T>{
        private T data ; //节点的值
        private Node<T> next;
        public Node(T data){
            this(data, null);
        }
        public Node(T data, Node<T> next) {
            this.data = data;
            this.next = next;
        }
        public T getData() {
            return data;
        }
        public void setData(T data) {
            this.data = data;
        }
        public Node<T> getNext() {
            return next;
        }
        public void setNext(Node<T> next) {
            this.next = next;
        } //节点的后继节点
    }
    
    public static void main(String[] args) {
        Node<Integer> n6 = new Node(6);
        Node<Integer> n5 = new Node(5, n6);
        Node<Integer> n4 = new Node(4, n5);
        Node<Integer> n3 = new Node(3, n4);
        Node<Integer> n2 = new Node(2, n3);
        Node<Integer> n1 = new Node(1, n2);
        n6.setNext(n3);
　　　　 //Node n = circleStartNode(n1);
        Node n = circleStartNode2(n1);
        System.out.println(n.getData());
    }

    /**
     * 查找环的入口节点
     * 解法一：使用Set集合
     * @param n1
     * @return
     */
    public static Node circleStartNode(Node<Integer> n1) {
        // TODO Auto-generated method stub
        if(n1 == null){
            return null;
        }
        Set<Node> set = new HashSet<Node>();
        while(n1 != null && set.add(n1)){ //利用set集合不能存储重复数据的特性
            n1 = n1.getNext();
        }
        return n1;
    }
    /**
     * 解法二：使用两个指针解决
     * 1、首先得到环中节点的个数
     * 2、利用两个指针进行查找
     * @param n1
     * @return
     */
    public static Node circleStartNode2(Node<Integer> n1) {
        int size = circleSize(n1); //得到环的节点个数
        Node p1 = n1;
        Node p2 = n1;
        while(size > 0){
            p1 = p1.next;
            size--;
        }
        while(p1 != null && p2 != null){
            if(p1 == p2){
                return p1;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        return null;
    }
    /**
     * 找到链表相遇的节点
     * @param n
     * @return
     */
    public static Node meetingNode(Node n){
        if(n == null){
            return null;
        }
        Node p1 = n; //慢指针，每次移动一个
        Node p2 = n; //快指针，每次移动两个
        while(true){
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1 == p2){ //相遇的节点
                return p1;
            }
        }
    }
    public static int circleSize(Node<Integer> n1) {
        int size = 0;
        if(n1 == null){
            return -1;
        }
        //利用快慢指针得到第一次相遇的节点，此节点必然在环中，然后遍历进行计数
        Node p = meetingNode(n1);
        Node p1 = p.next;
        while(p1 != null){
            if(p1 != p){
                size++;
                p1 = p1.next;
            }else{
                size++;
                break;
            }
        }
        return size;
    }
}

求链表中环的入口节点

相关推荐