剑指offer16

2019-07-08  本文已影响0人  MonarchNie

题目描述

给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

解题思路分析

代码实现

public ListNode entryNodeOfLoop(ListNode pHead) {
    if (pHead == null) {
        return null;
    }
    //先找到环中的某个节点
    ListNode meetingNode = meetingNode(pHead);
    int count = 1;
    ListNode node = meetingNode;
    //计算环中的节点个数
    while (node.next != meetingNode) {
        count++;
        node = nodex.next;
    }
    ListNode node1 = pHead, node2 = pHead;
    //先让一个节点走节点个数步
    for (int i = 0; i < count; i++) {
        node1 = node1.next;
    }
    //开始找到环的入口节点
    while (node1 != node2) {
        node1 = node1.next;
        node2 = node2.next;
    }
    return node2;
}

//返回环中的节点
public ListNode meetingNode(ListNode pHead) {
    //分别声明快指针和慢指针
    ListNode slow = pHead, fast = pHead.next;
    while (fast != null) {
        if (fast == slow) {
            return fast;
        }
        slow = slow.next;
        fast = fast.next;
        //防止空指针异常
        if (fast != null) {
            fast = fast.next;
        }
    }
    return null;
}
上一篇下一篇

猜你喜欢

热点阅读