欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

21、链表中环的入口节点——剑指offer

程序员文章站 2022-06-17 17:21:55
...

链表中环的入口节点

问题描述:链表中环的入口节点

21、链表中环的入口节点——剑指offer

    首先考察基本功,有两种方法,第一种建立一个set集合,添加失败的时候说明找到了重复的,但是需要额外的On的空间;第二种方法是用快慢指针。

    本方法思想:分为3步,代码有注释

        1、判断是否有环:一快指针,一慢指针,快指针追上满指针则有;
        2、判断环的节点个数:一个指针走,一个指针静止,相等时走的次数就是环的个数count

        3、找到入口节点:先让快指针走count,然后同步遍历,找到相同就是入口节点

21、链表中环的入口节点——剑指offer

持续更新...

代码附下

Java实现:

package 链表中环的入口节点;
/**
 * 第一种方法:建立一个set集合,添加失败的时候说明找到了重复的 第二种方法: 1判断是否有环:一快指针,一慢指针,快指针追上满指针则有 2判断环的节点个数
 * 3找到入口节点:先让快指针走count,然后同步遍历,找到相同就是入口节点
 * 
 * @author user
 *
 */

21、链表中环的入口节点——剑指offer

class ListNode {
    int val;
    ListNode next = null;
    public ListNode(int val) {
        this.val = val;
    }
}
public class Test {
    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        ListNode n6 = new ListNode(6);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = n3;
        findEnt(n1);
        // System.out.println(node.val);
    }
    private static ListNode findEnt(ListNode head) {
        ListNode first = head;
        ListNode second = head.next;
        while (first != second) {
            if (second.next.next != null) {
                second = second.next.next;
                first = first.next;
            } else {
                // 到最后是空 说明没有环
                return null;
            }
        }
        System.out.println("有环!!!");
        // 有环 接下来计算环内的节点数
        int count = numberOfNode(first);
        System.out.println("环内节点数为:" + count);
        // 从当前节点往后走count个 就是入口节点
        for (int i = 0; i < count; i++) {
            first = first.next;
        }
        // 接下来就是找入口
        ListNode en = findEntCore(head, count);
        System.out.println("起始点为:" + en.val);
        return en;
    }
    private static ListNode findEntCore(ListNode head, int count) {
        ListNode first = head;
        ListNode second = head;
        for (int i = 0; i < count; i++) {
            first = first.next;
        }
        while (first != second) {
            first = first.next;
            second = second.next;
        }
        return first;
    }
    private static int numberOfNode(ListNode node) {
        int count = 1;
        ListNode temp = node.next;
        while (node != temp) {
            count++;
            temp = temp.next;
        }
        return count;
    }
}

持续更新...欢迎赞赏!21、链表中环的入口节点——剑指offer

主页:https://blog.csdn.net/ustcer_93lk/article/details/80374008

如果有问题,欢迎大家留言,有更好的方法也期待大家告知。