java - 查找子列表的索引

Question

算法题。假设我们有一个列表 1, 2, 3, 4, 5和一个子列表 2, 3 ，算法应返回 1，因为子列表从索引 1 开始。如果指定的子列表不存在，算法应返回 -1。

我们有一个定义的Node数据结构，如下所示。

Node.java

private static class Node {

    public Node(int value) {
        this.value = value;
        this.next = null;
    }

    int value;
    Node next;
}

我提出了以下算法，但我很好奇它在性能方面是否会比该算法更好。

public static int findSublistIndex(MyLinkedList list, MyLinkedList sublist) {
    if (list.head == null || sublist.head == null) {
        return -1;
    }

    int index = -1;

    for (Node l = list.head; l != null; l = l.next) {
        index ++;

        // encountered a value that is equal to the first value of a sublist
        if (l.value == sublist.head.value) {
            Node n = l;

            // check the rest of the sublist
            for (Node s = sublist.head; s != null; s = s.next) {
                if (n.value == s.value && s.next == null) {
                    return index;
                } else if (n.value == s.value) {
                    n = n.next;
                } else {
                    // the pointer should be set to l here to skip repeating? l = n;? -- doesn't work!
                    break;
                }
            }
        }
    }

    return -1;
}

此外，我还想练习更多这样的列表算法问题。有没有类似问题的网站可以推荐？

Answer 1

更好的算法是 KMP algorithm 。它用于进行子字符串搜索，也可以在您的情况下使用。它的时间成本是O(n+k)，所以它是一个线性算法，而你的算法是O(nk)，其中n是列表的长度，k是子列表的长度。

更多算法挑战或代码挑战，您可以在 codeForces 中找到或leetcode