破解编码面试通告链表

Question

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

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

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

我的解决方案是跟踪在数组列表中看到的节点，然后一旦我到达一个我已经看到的节点，那么我就知道它是循环开始的节点。

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为列表的大小。