单链表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的实现

回答

相关问题