破解编码面试循环链表

Question

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

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

示例：输入：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;
        }
    }
}

节点class:

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

就 space 复杂性而言，是的，她的解决方案显然更好。您的解决方案要求您维护所有已经看到的节点，即 O(n)，n 是列表的大小。

破解编码面试循环链表

Cracking the Coding Interview Circular Linked List

java

linked-list

circular-list