The idea is to find segments of the second linked list that are identical to the first linked list, and add whichever node directly follows to a list that will be returned. So, if my first linked list is
h -> e -> y -> None
and my second is
h -> e -> y -> d -> u -> d -> e -> None
my output should be [d].

I've verified that the linked lists have been created properly, but will just add their contents as comments to keep things simple:

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))

The bottom print function prints an output list of [8], when I should be getting [8, 9]. Is there something obvious I'm overlooking?

CodePudding user response：

Your main issue is that you need to make two checks when you find the first value in the corpus that matches your target list. First you need to check if the rest of the target list matches. And second, you need to check the rest of the corpus for the whole main list. Unfortunately, you don't really want to use the same recursive function for both, or you'll match the end of the target list anywhere they appear (regardless of whether they follow the earlier parts). Maybe you could add a flag to stop that, but it would be conceptually simpler with a separate function.

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

Note that since both of these functions are tail recursive, you can easily turn them into loops, and if you want, nest the loops in a single function:

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

CodePudding user response：

I translated your function and it seems to work as expected. Is it possible there is some problem with your linked list setup?

# 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]