Создание рекурсивной функции в 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) 
    ) 

EDIT: Или для меньшего количества логических операций,

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