單鏈表Python的實現

我想從python單向鏈表中倒數第二個元素。下面是我的實現：單鏈表Python的實現

class ListNode: 
    def __init__(self, data, next): 
     self.data = data 
     self.next = next 

def make_arr(xx, arr): 
    if xx == None: 
     return arr 
    else: 
     arr.insert(0, xx.data) 
     make_arr(xx.next, arr)

當我做到以下幾點：

lst = ListNode(1, ListNode(2, ListNode(3, ListNode(3, None)))) 
print make_arr(lst, [])[2]

我得到的錯誤：

'NoneType' object has no attribute '__getitem__'

來源

2014-02-09 user2837048

除了你的'None'問題，你正在建立'arr'作爲你的鏈表的反轉版本。這是故意的嗎？ –

是的，因爲一旦我將它倒過來......我將能夠檢索倒序列表的第三個元素，它將成爲原始元素的倒數第二個元素。（線性算法） – user2837048

你也不回在make_arrarr ...

編輯：您的代碼版本

def make_arr(xx, arr): 
    if xx == None: 
     return arr 

    # No need for the else, in this case 
    arr.insert(0, xx.data) 
    return make_arr(xx.next, arr)

來源

2014-02-09 23:43:40

我不明白，當我達到無，我顯然返回arr。 – user2837048

是的......但是你已經實現了一個遞歸函數，一旦你找到'xx == None'的情況，Python就會返回一級並看到這個：'make_arr（xx.next，arr）'......它對返回的值沒有任何作用，並繼續返回......'None'。依此類推，直到它解開。 –

單鏈表Python的實現

回答

相關問題