架构师训练营 week08 作业

public class IsListsIntersection {
    //比较最后一个节点是否是同一个节点，无环情况
    public static boolean isListsInters(Node h1, Node h2){
        if (h1 == null || h2 == null){
            return false;
        }
        while (h1.getNext() != null){
            h1 = h1.getNext();
        }
        while (h2.getNext() != null){
            h2 = h2.getNext();
        }
        return h1 == h2;
    }
    public static void main(String[] args){
        Node h1 = new Node(1);
        Node n2 = new Node(2);
        Node h2 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        h1.setNext(n2);
        n2.setNext(n4);
        h2.setNext(n4);
        n4.setNext(n5);
        System.out.println("h1与h2相交："+IsListsIntersection.isListsInters(h1,h2));
    }
}
 //求出第一个相交节点，即得出相交的节点列，无环情况
    public static Node getFirstIntersList(Node h1, Node h2){
        //计算两个链表之间的长度差距
        int distance = Node.getLength(h1) - Node.getLength(h2);
        //对较长的链表进行移动，直到两者长度一致
        if (distance > 0){
            h1 = IsListsIntersection.movePosD(h1,distance);
        }else{
            h2 = IsListsIntersection.movePosD(h2,distance);
        }
        //从头开始，对节点进行逐对比较
        while ( h1 != null && h2 != null){
            if (h1 == h2){
                return h1;
            }
            h1 = h1.getNext();
            h2 = h2.getNext();
        }
        return null;
    }
    //将指针后移dis个位置
    public static Node movePosD(Node h, int dis){
        while (h != null && dis >0){
            h = h.getNext();
            dis--;
        }
        return h;
    }
    //打印链表
    public static void printList(Node h){
        while (h != null){
            System.out.print(h.getData()+" ");
            h = h.getNext();
        }
    } 
    public static void main(String[] args){
        Node h1 = new Node(1);
        Node n2 = new Node(2);
        Node h2 = new Node(3);
        Node n4 = new Node(4);
        Node n5 = new Node(5);
        h1.setNext(n2);
        n2.setNext(n4);
        h2.setNext(n4);
        n4.setNext(n5);
        Node commonList = IsListsIntersection.getFirstIntersList(h1,h2);
        IsListsIntersection.printList(commonList);
    }