这个想法是找到第二个链表中与第一个链表相同的段，并将直接跟随的节点添加到将回传的串列中。所以，如果我的第一个链表是
h -> e -> y -> None
并且我的第二个是
h -> e -> y -> d -> u -> d -> e -> None
我的输出应该是[d].

我已验证链接串列已正确创建，但只会将其内容添加为注释以保持简单：

def find_sublist(list_start_node, corpus_start_node, output=[]):
    if corpus_start_node is None:
        return output
    elif list_start_node is None:
        output.append(corpus_start_node.item)
        return find_sublist(myList.head, corpus_start_node)
    elif list_start_node.item is corpus_start_node.item:
        return find_sublist(list_start_node.next_node, corpus_start_node.next_node)
    else:
        return find_sublist(myList.head, corpus_start_node.next_node)

# myList: 3 -> 7 -> None
# myCorpus: 3 -> 7 -> 8 -> 2 -> 34 -> 77 -> 21 -> 3 -> 7 -> 9 -> 2 -> 34 -> 88 -> 9 -> None

print(find_sublist(myList.head, myCorpus.head))

底部打印功能打印输出串列[8]，当我应该得到[8, 9]。有什么明显的我忽略了吗？

uj5u.com热心网友回复：

您的主要问题是，当您在语料库中找到与目标串列匹配的第一个值时，您需要进行两次检查。首先，您需要检查目标串列的其余部分是否匹配。其次，您需要检查整个主串列的其余语料库。不幸的是，您并不想对两者都使用相同的递回函式，否则您将匹配目标串列的末尾出现的任何位置（无论它们是否遵循前面的部分）。也许您可以添加一个标志来阻止它，但是使用单独的函式在概念上会更简单。

def matcher(needle, haystack):
    if haystack is None:  # failure case #1, we've run out of haystack
        return None
    if needle is None:    # success case, return the next haystack item
        return haystack.item
    if needle.item != haystack.item:  # falure case #2, a mismatch
        return None
    return matcher(needle.next_node, haystack.next_node)  # recurse

def searcher(needle, haystack, results=None):
    if results is None:   # avoid using a mutable default argument
        results = []

    if haystack is None:  # base case, we've searched the whole haystack
        return results

    match = matcher(needle, haystack) # test current position in haystack
    if match is not None:
        results.append(match)

    return searcher(needle, haystack.next_node, results)  # recurse

请注意，由于这两个函式都是尾递回的，因此您可以轻松地将它们转换为回圈，如果需要，可以将回圈嵌套在一个函式中：

def iterative_search_and_match(needle, haystack):
    results = []
    while needle and haystack:  # search loop
        match_needle = needle
        match_haystack = haystack
        while match_needle and match_haystack:  # match loop
            if match_needle.item != match_haystack.item:
                break
            match_needle = match_needle.next_node
            match_haystack = match_haystack.next_node
        else:  # this doesn't run if the break was hit!
            if match_haystack:
                results.append(match_haystack.item)
        needle = needle.next_node
        haystack = haystack.next_node
    return results

uj5u.com热心网友回复：

我翻译了你的功能，它似乎按预期作业。您的链表设定可能有问题吗？

# Setup
start_corpus = None
for x in reversed([3, 7, 8, 2, 34, 77, 21,
                   3, 7, 9, 2, 34, 88, 9]):
    start_corpus = (x, start_corpus)

start_word = (3, (7, None))

##################

def find_sublist(word, corpus):
    if corpus is None:
        return
    elif word is None:
        yield corpus[0]
        yield from find_sublist(start_word, corpus)
    elif word[0] == corpus[0]:
        yield from find_sublist(word[1], corpus[1])
    else:
        yield from find_sublist(start_word, corpus[1])

print(list(find_sublist(start_word, start_corpus)))
# [8, 9]