python - 在 Python 3 中创建递归函数

Question

到目前为止，这就是我现在拥有的

class X:
    def __init__(self,value,next=None):
        self.value = value
        self.next  = next

def linkedlist(l):
    if l == []:
        return None
    beg = end = X(l[0])
        for v in l[1:]:
            end.next = X(v)
            end = end.next
    return beg

lst1 = linkedlist(['a', 'b', 'c''])
lst2 = linkedlist(['a', 'b', 'c'])
lst3 = linkedlist(['c', 'a', 'b'])

我正在尝试创建一个递归函数来确定两个链表 lst 1 和 lst 2 是否相同。如果是，它将返回 True，否则返回 False。

def is_same(lst1, lst2):
    if lst1.next == None or lst2.next == None: 
        return None 
    else:
        if lst1.next == lst2.next:
            return X(is_same(lst1.next, lst2.next))
        else:
            return True

我知道我的递归函数是错误的，但我遇到了麻烦，因为它一直给我错误。每次我输入时，“is_same”函数都会返回 True:

is_same(lst1, lst2)
is_same(lst1, lst3) # This should be False

Answer 1

有几个问题。

1. 这不处理空列表(None)。
2. lst1.next == lst2.next 比较节点，而不是值。
3. 从不比较第一个值。
4. 出于某种原因，您正在调用构造函数 X。

我想你想要这样的东西

def is_same(lst1, lst2):
    return not lst1 and not lst2      \ 
        or lst1 and lst2              \
        and lst1.value == lst2.value  \
        and is_same(lst1.next, lst2.next)

可选地，为了清楚起见，您可能希望加入括号(以防有人不知道and 和or 的操作顺序)。

def is_same(lst1, lst2):
    return (not lst1 and not lst2) or (
        lst1 and lst2
        and lst1.value == lst2.value
        and is_same(lst1.next, lst2.next)
    )

编辑:或者，为了减少 bool 运算，

def is_same(lst1, lst2):
    if lst1:
        return lst2                       \
            and lst1.value == lst2.value  \
            and is_same(lst1.next, lst2.next)
    return not lst2