7_2判断两个单链表是否相交，若相交，求出第一个交点

转载请注明出处：http://www.cnblogs.com/wuzetiandaren/p/4251372.html

声明：现大部分文章为寻找问题时在网上相互转载，此博是为自己做个记录记录，方便自己也方便有类似问题的朋友，本文的思想也许有所借鉴，但源码均为本人实现，如有侵权，请发邮件表明文章和原出处地址，我一定在文章中注明。谢谢。

题目：7_2判断两个单链表是否相交，若相交，求出第一个交点。

题目分析：

创建A，B两个单链表,将B的尾部指向头部,若两个单链表相交,则交点必为环的入口，这就又变成上边判断一个单链表是否有环的问题了。

注： 若两个单链表相交，则相交之后的那些节点比都是一样的(相交之后的长度是一样的)，否则若一长一短或者相交之后有分叉，则在短链表末尾或者分叉节点处，该节点将有两个next分别指向两边的链表，这就不是单链表了。

源码实现：

package com.interview;

/**
 * 判断两个单链表是否相交，若相交，求出第一个交点
 * 方法：创建A，B两个单链表,将B的尾部指向头部,若两个单链表相交,则交点必为环的入口
 *   若两个单链表相交，则相交之后的那些节点比都是一样的(相交之后的长度是一样的)，
 *   否则若一长一短或者相交之后有分叉，则在锻炼表末尾或者分叉节点处，该节点将有
 *   两个next分别指向两边的链表，这就不是单链表了
 * @author wjh
 *
 */
public class _7_2JudgeListCross {

    /**
     * @param args
     */    
    //分别记录相交前A表的长度,B链表(圈)的长度,第一次相遇时慢指针走的总长度
    public static int x=0, y=0, k=0;   
    public static void main(String[] args) {
        //1)创建两个相交的链表
        Node nodeA = createList("A", 28);
        Node nodeB = createList("B", 3);
        Node tail = createTail(3);
        nodeA = merge(nodeA, tail);
        nodeB = merge(nodeB, tail);        
        //2)将B的尾节点指向B的第一个节点 ,此时若相交,A的结构就变成带环单链表了，
            //若不相交则遍历A会走到null
        Node r = findTail(nodeB);  //若要求A B的长度，则在上面遍历nodeA,nodeA
        r.next = nodeB.next;
        judge(nodeA);

    }
    
    
    //创建带头节点的无环单链表的相较之前的部分
    public static Node createList(String name, int k){
        /**  1)用尾插法构建单链表，此处构建有环单链表，让node24指向node6*/
        Node first = new Node(null,null);    //头节点
        Node r = first;   //指向链表的尾节点
        for(int i=1;i<=k;i++){  //根据传入参数创建相交之前的部分节点
            Node node = new Node("猫狗_"+name+"_"+i,null);
            r.next = node;
            r = node;
        }
        r.next = null;       //若是构建无环单链表，此处   r.next = null;
        return first;
    }
    
    //创建带头节点的无环单链表的相较之后的相同的部分
    public static Node createTail(int k){
        Node first = new Node(null,null);    //头节点
        Node r = first;   //指向链表的尾节点
        for(int i=1;i<=k;i++){  //创建相交之后的部分节点
            Node node = new Node("相同节点@"+i,null);
            r.next = node;
            r = node;
        }
        r.next = null;       //若是构建无环单链表，此处   r.next = null;
        return first;
    }
    
    //将相交之前和相交之后的链表穿起来
    public static Node merge(Node first, Node second){
        Node r = first;   //记录前面链表的尾部节点
        while(r.next!=null){
            r = r.next;
        }
        //因为second是后面链表的头节点，是空的，头节点下一个节点才是真正的节点
        r.next = second.next;
        return first;
    }
    
    //找到一个链表的尾节点
    public static Node findTail(Node node){
        Node r = node;   //记录前面链表的尾部节点
        while(r.next!=null){
            r = r.next;
        }
        return r;
    }

    //判断是否有环
    public static void judge(Node first){
        /**  2)判断是否有环若pq先重合则有环，若q先指向null,则无环    */
        Node p = first.next;
        Node q = first.next;
        String flag = "0";  //标记有环还是无环,0-无环,1-有环
        if(p==null){     //空链表
            System.out.println("链表为空！");
            return;
        }
        k=1;
        while(q.next!=null && q.next.next!=null){
            k++;      //记录相遇时p指针走的长度,k从0开始，因为k已经加过1了才判断pq是否相等
            p=p.next;
            q=(q.next).next;
            if(q.equals(p)){
                flag="1";
                System.out.println("p和q相遇了,这两个单链表相交！");
                break;
            }
        }
        
        /**  3)有环的时候求环的入口节点    */
        if(flag.equals("1")){    //有环
            p=first.next; //p重新指向第一个节点
            searchEnter(p,q);
        }
        else{   //是因为q走到了尽头才跳出循环的，无环
            System.out.println("这两个单链表不相交！");
        }
    }
    
    //求环的入口节点    
    public static void searchEnter(Node p, Node q){
        x=1;
        while(!q.equals(p)){
            x++;  //求圈外长度
            p=p.next;
            q=q.next;
        }
        Node r = q.next;   //为了求圈长设定的
        y = 1;     //求圈长度
        while(r!=q){
            r = r.next;
            y++;
        }
        System.out.println("相交节点是A链表中的第"+ x+"个节点！");
        System.out.println("相交节点的名字为: "+ p.name);
        System.out.println("B链表的长度是："+ y);
        System.out.println("第一次相遇时，慢指针在B圈内走的长度为："+ (k-x));
        System.out.println("第一次相遇时，快指针在B圈内走了："+ (k/y)+"圈");
        System.out.println("第二次相遇时，快指针在B圈内又走了："+ (k/y-1)+"圈");
    }
    
    
    //创建一个私有的节点类
    private static class Node {
        public String name;
        public Node next;
        public Node(String name, Node next) {
            super();
            this.name = name;
            this.next = next;
        }
    }
}

运行结果：

1.有交点：

p和q相遇了,这两个单链表相交！
相交节点是A链表中的第29个节点！
相交节点的名字为: 相同节点@1
B链表的长度是：6
第一次相遇时，慢指针在B圈内走的长度为：2
第一次相遇时，快指针在B圈内走了：5圈
第二次相遇时，快指针在B圈内又走了：4圈

2.无交点：

这两个单链表不相交！