算法-链表-找到单链表入环节点

2022-4-7 diaba 笔试题

问题

判断一个单链表是否存在环，如果存在返回入环节点

要求

时间复杂度O(N)，空间复杂度O(1)

方案

快慢指针：从头结点开始，快指针一次走两步，满指针一次走一步，如果这两个指针相遇后，快指针回到头结点，两个指针一起开始走，每次走一步，再次相遇的节点即是入环节点

代码

package com.jiucaiyuan.net.algrithm.linked;

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

/**
 * 【问题】：判断一个单链表是否存在环，如果存在返回入环节点
 * 【方法】快慢指针：从头结点开始，快指针一次走两步，满指针一次走一步，
 * 如果这两个指针相遇后，快指针回到头结点，两个指针一起开始走，
 * 每次走一步，再次相遇的节点即是入环节点
 *
 * @Author jiucaiyuan  2022/4/7 23:12
 * @mail services@jiucaiyuan.net
 */
public class FindLoopNode {

    /**
     * 确实简洁
     * @param head
     * @return
     */
    public static ListNode getLoopNode(ListNode head){
        if(head == null || head.next == null || head.next.next == null){
            return null;
        }
        ListNode n1 = head.next;
        ListNode n2 = head.next.next;
        while(n1!= n2) {
            if (n2.next == null || n2.next.next == null) {
                return null;
            }
            n1 = n1.next;
            n2 = n2.next.next;
        }
        n2 = head;
        while (n1 != n2){
            n1 = n1.next;
            n2 = n2.next.next;
        }
        return n1;
    }

    public static ListNode entryNodeOfLoop(ListNode pHead) {

        if (pHead == null) {
            return null;
        }
        ListNode fast = pHead;
        ListNode low = pHead;
        boolean second = false;
        while (low != null && fast != null && fast.next != null) {
            if (fast == low) {
                if (second) {
                    return fast;
                }
                if (fast != pHead && low != pHead) {
                    fast = pHead;
                    second = true;
                    continue;
                }
            }
            low = low.next;
            if (second) {
                fast = fast.next;
            } else {
                fast = fast.next.next;
            }
        }
        //如果快慢指针有一个为null，则不存在环
        return null;
    }

    public static void print(ListNode head) {
        Set<ListNode> set = new HashSet<>();
        System.out.println("-------------------------");
        while (head != null) {
            if(!set.contains(head)){
                set.add(head);
            }else{
                System.out.print("\t入环节点="+head.val);
                break;
            }
            System.out.print("\t"+head.val);
            head = head.next;
        }
        System.out.println();
        System.out.println("-------------------------");
    }

    public static void main(String[] args) {
        int[] arrays = {1, 2, 3, 4, 15,20,21,43,25,8,5,40};
        int entryNodeValue = 21;
//        int[] arrays = {0};
        ListNode head = new ListNode(arrays[0]);
        ListNode tail = null;
        ListNode entryNode = null;
        if (arrays.length > 1) {
            ListNode tmp = new ListNode(arrays[1]);
            head.next = tmp;
            for (int i = 2; i < arrays.length; i++) {
                tail = new ListNode(arrays[i]);
                if (arrays[i] == entryNodeValue) {
                    entryNode = tail;
                }
                tmp.next = tail;
                tmp = tmp.next;
            }
        }
        tail.next = entryNode;
        print(head);
        System.out.println("找到的入环节点是："+entryNodeOfLoop(head));
    }
}

输出结果

-------------------------
	1	2	3	4	15	20	21	43	25	8	5	40	入环节点=21
-------------------------
找到的入环节点是：ListNode{val=21}

Process finished with exit code 0