题解 | #链表中环的入口结点#

目录

• 解题思路 1
• 代码实现
• 解题思路 2
• 代码实现
• 解题思路 3
• 代码实现

解题思路 1

1. 修改节点设置标记
2. 将遍历过的节点的标记置为 1
3. 当当前节点的标记为 1 即为入口节点

如果使用这种方法，我还可以通过将值的 int 类型，改为 String 类型，将每个遍历过的节点的值首位加一个标识位。

代码实现

class ListNode {
    int val;
    int tag;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        while(true){
            if(pHead.next == null)return null;
            if(pHead.tag == 1)return pHead;
            pHead.tag = 1;
            pHead = pHead.next;
        }
    }
}
// 运行时间：54ms	超过6.64% 用Java提交的代码
// 占用内存：12496KB	超过51.59%用Java提交的代码

时间复杂度: $O(n)O(n)$

空间复杂度: $O(1)O(1)$

解题思路 2

1. 用列表存储已遍历过的节点
2. 检查当前节点是否存在列表里面
3. 存在就返回当前节点

代码实现

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        List list = new ArrayList();
        while(true){
            if(pHead.next == null)return null;
            if(list.indexOf(pHead)!=-1)return pHead;
            list.add(pHead);
            pHead = pHead.next;
        }
    }
}
// 运行时间：98ms	超过0.25% 用Java提交的代码
// 占用内存：13592KB	超过40.25%用Java提交的代码

这种方法还没有第一种方法快

解题思路 3

1. 设置两个节点遍历速度不一样
2. 如果是环形那么总会相遇的
3. 再设置一个节点，当前再次相遇就可以判断是入口节点

代码实现

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if(pHead == null)return null;
        ListNode fast = pHead;
        ListNode last = pHead;
        while(true){
            if(fast.next == null||fast.next.next==null)return null;
            last = last.next.next;
            fast = fast.next;
            if(last==fast){
                while(true){
                    if(pHead == last)return pHead;
                    pHead = pHead.next;
                    last = last.next;
                }
            }
        }
    }
}
// 运行时间：49ms	超过8.64% 用Java提交的代码
// 占用内存：12588KB	超过50.64%用Java提交的代码

时间复杂度: $\mathrm{不}\mathrm{稳}\mathrm{定}不稳定$

空间复杂度: $O(1)O(1)$