面试题 56

1 题目描述

一个链表中包含环，如何找出环的入口节点？例如下图的 3 结点即为入口节点

2 算法描述

• 找到环内的任何一个结合：利用两个指针（前指针和后指针），前指针一次性前进两步，后指针一次性前进一步，当前指针与后指针再次相遇时，那么说明次链表中必定存在环，而且相遇的节点必定在环里面。
• 确定环内节点的数量：设定一个指针从上次得到的节点 A 开始移动，当指针再次移动到 A 时，说明指针已经在环立面绕了一圈。
• 再次设立两个指针，头指针向前移动 nums（nums 是环内节点的个数），然后同时移动，直到两个指针指向同一个节点。此节点即为链表环的入口节点。
  

3 java 语言实现

package 链表中换的入口结点;

public class EntryNodeOfLoop {
    public static void main(String[] args) {
        //首先随机生成一个链表
        ListNode list=buliderList(10);
        //构造一个环,第后一个结点指向第三个节点
        buliderRing(list,3,10);

        //showData(list,10);

        //找到第链表中环的入口点
        ListNode entry=entryNodeOfLoop(list);   

        System.out.print(entry.data);


    }
    private static ListNode entryNodeOfLoop(ListNode list) {
        //首先确定环中的某一个节点
        ListNode someNode=getSomeNodeInRing(list);
        //然后确定环中节点的个数
        int len=1;
        ListNode temp=someNode.next;
        while(temp!=someNode){
            temp=temp.next;
            len++;
        }
        //韩后利用在链表寻找倒数第 K 个元素 的算法进行查找
        ListNode first=list;
        ListNode second=list;
        for(int i=0;i<len;i++){
            second=second.next;
        }
        while(first!=second){
            first=first.next;
            second=second.next;
        }
        return second;
    }
    private static ListNode getSomeNodeInRing(ListNode list) {
        /*
         * 算法:
         * 就是设立两个指针,从头结点开始,一个指针一次性走一步,另一个指针一次性走两步,直到两个指针相遇
         */
        ListNode first=list;
        ListNode second=list.next.next;
        while(second!=first){
            first=first.next;
            second=second.next.next;
        }
        return first;
    }
    private static void showData(ListNode list,int len) {
        ListNode node=list;
        while(list!=null&&len>0){
            System.out.println(node.data);
            node=node.next;
            len--;
        }

    }
    private static void buliderRing(ListNode list,int to, int len) {
        ListNode toNode=null;
        ListNode fromNode=null;
        ListNode temp=list;
        for(int i=0;i<len;i++){
            if(i==2){
                toNode=temp;
            }
            if(temp.next==null){
                fromNode=temp;
            }
            temp=temp.next;
        }
        fromNode.next=toNode;
    }
    private static ListNode buliderList(int len) {
        ListNode head = new  ListNode(1,null);
        for(int i=0;i<len-1;i++){
            ListNode node = new ListNode(i+2,head.next);
            head.next=node;
        }
        return head;
    }
    private static class ListNode{
        public int data;
        public ListNode next;
        public ListNode(int data,ListNode next){
            this.data=data;
            this.next=next;
        }
    }
}