数据结构学习之线性表（JAVA）

分析： 先给出六个空节点，分别为小于区域的头和尾节点、等于区域的头和尾节点、大于区域的头和尾节点，遍历该链表，利用while循环形成三个链表即三个区域所属数的保留原始位置的子链表，然后三个链表首位相接即可。

问题二：

给你两个单链表的头节点 headA 和 headB,请你找出并返回两个单链表相交的起始节点。
如果两个链表没有交点，返回 null 。

代码：

public static ListNode getIntersectNode(ListNode head1,ListNode head2){
        if (head1==null||head2==null){
            return null;
        }
        ListNode loop1 = getLoopNode(head1);
        ListNode loop2 = getLoopNode(head2);
        if (loop1==null&&loop2==null){
            noLoop(head1,head2);
        }
        if (loop1!=null&&loop2!=null){
            return bothLoop(head1,head2,loop1,loop2);
        }
        return null;
    }

 

    //判断一个单链表是否有环存在 并且返回入环节点
    public static ListNode getLoopNode(ListNode head){
        if (head == null|| head.next == null){
            return null;
        }
        ListNode ln1 = head.next;
        ListNode ln2 = head.next.next;
        while (ln1!=ln2){
            if (ln2.next==null||ln2.next.next==null){
                return null;
            }
            ln2 = ln2.next.next;
            ln1 = ln1.next;
        }
        ln2 = head;
        while (ln1!=ln2){
            ln1 = ln1.next;
            ln2 = ln2.next;
        }
        return ln1;
    }

//无环情况
    public static ListNode noLoop(ListNode head1,ListNode head2){
        if (head1==null||head2==null){
            return null;
        }
        ListNode cur1 = head1;
        ListNode cur2 = head2;
        int n = 0;
        while (cur1.next!=null){
            n++;
            cur1 = cur1.next;
        }
        while (cur2.next!=null){
            n--;
            cur2 = cur2.next;
        }
        if (cur1!=cur2){
            return null;
        }
        cur1 = n>0 ? head1:head2;
        cur2 = cur1==head1 ? head2:head1;
        n = Math.abs(n);
        while (n!=0){
            n--;
            cur1 = cur1.next;
        }
        while (cur1!=cur2){
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return cur1;
    }

//均有环情况
    public static ListNode bothLoop(ListNode head1,ListNode head2,ListNode loop1,ListNode loop2){
        ListNode cur1 = null;
        ListNode cur2 = null;
        if (loop1==loop2){
            cur1 = head1;
            cur2 = head2;
            int n = 0;
            while (cur1!=loop1){
                n++;
                cur1 = cur1.next;
            }
            while (cur2!=loop2){
                n--;
                cur2 = cur2.next;
            }
            cur1 = n>0 ? head1:head2;
            cur2 = cur1==head1 ? head2:head1;
            n = Math.abs(n);
            while (n!=0){
                n--;
                cur1 = cur1.next;
            }
            while (cur1!=cur2){
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }else {
            cur1 = loop1.next;
            while (cur1!=loop1){
                if (cur1==loop2){
                    return loop1;
                }
                cur1 = cur1.next;
            }
            return null;
        }
    }

分析：

两链表存在相交的三种情况：

 1.无环情况下只需记录较长链表与较短链表的长度差，然后先让较长链表遍历完长度为长度差的部分，然后两个链表一起遍历，相遇的节点即为相交的起始节点。

2.第一种有环情况思想与无环情况相似，先判断两个链表的如环节点是否为同一点来区分第二和第三种情况，若为同一点，即为第二种情况，然后用无环情况的获取起始节点相同的方法来得到此时相交的起始节点。

3.最后一种情况更简单，若入环节点不是同一个节点，则返回任意一个入环节点即可。

关键：如何判断一个有环链表的入环节点？

让慢指针一次走一步，快指针一次走两步，当快慢指针在环中相遇时，记录下这个相遇点M。然后我们定义指针cur从链表头开始走，让刚才在相遇点的slow指针也开始走，他们每次都走一步，他们的相遇点一定为环的入口点。（这是一个可证明的事实）