查找索引子列表

问题描述：

算法问题。假设我们有一个列表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; 
}

另外，我想要练习一些更多列表算法问题。任何有此类问题的网站推荐？

我投票作为题外话，因为它要求工作算法进行审查，并建议地方练习编程关闭这个问题。 – dasblinkenlight

@dasblinkenlight那么问题是什么？我正在寻求算法的可能改进。为什么不征求建议在哪里练习...... – wesleyy

这个问题是堆栈溢出的主题。请参阅[代码评论网站]（https://codereview.stackexchange.com/）来发布类似的问题。此外，要求提供异地资源建议的问题对于该网站来说是明显不合适的。 – dasblinkenlight

答

更好的算法是KMP algorithm。它用于做一个子字符串搜索，也可以用于你的情况。它的时间成本是O（n + k），所以它是一个线性算法，你的算法是O（nk），其中n是列表的长度，k是子列表的长度。

更算法的挑战或代码的挑战，你会发现在codeForces或leetcode

相关推荐