java - 破解编码面试循环链表

Question

关闭。这个问题是 opinion-based 。目前不接受答案。

---

想要改进这个问题吗？更新问题，以便 editing this post 可以用事实和引文来回答它。 .

已关闭 4 年前。

Improve this question

问题:给定一个循环链表，实现一个返回循环开头节点的算法。

定义:循环链表:一种(损坏的)链表，其中一个节点的下一个指针指向较早的节点，从而在链表中形成一个循环。

示例:输入:A -> B -> C -> D -> E -> C[与之前相同的 C]输出:C

我的解决方案是跟踪 ArrayList 中看到的节点，然后一旦到达我已经看到的节点，我就知​​道那是循环开始处的节点。

findBeginningLoop函数:

public Node findBeginningLoop(Node n) {
    ArrayList<Node> nodes = new ArrayList<Node>();
    Node pointer = n;
    while (true) {
        Node checkingNode = pointer;
        if (!nodes.contains(checkingNode)) {
            nodes.add(checkingNode);
        } else {
            return checkingNode;
        }
    }
}

节点类:

public class Node {
    Node next = null;
    int val;

    public Node(int d) {
        val = d;
    }

    public void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }   
}

她的解决方案是使用快指针和慢指针。这个解决方案更好吗？

Answer 1

就空间复杂度而言，是的，她的解决方案显然更好。您的解决方案要求您维护所有已见过的节点，即 O(n)，n 是列表的大小。