Python:移动链接列表“下一个”

Question

我正在努力破解第6版的编码面试，不确定他们对“下一步”的定义

他们定义“链表”的代码可以找到here。我尝试第二个练习，从随机链表的末尾元素中找出第k个。在

我的代码：

from LinkedList import LinkedList

def kth_to_last(ll, k):
    num_seen = 0
    length_list = count_length(ll)

    val = ll.head

    # ISSUE IS HERE
    while val.next != None:
        print 'hi'
        val.next = val.next.next

    """
    while num_seen < (length_list - k):
        val = val.next
        num_seen += 1
    """
    return val.next


# Counts length of LL
def count_length(ll):
    val = ll.head
    count = 1
    while val.next != None:
        count += 1
        val.next = val.next.next
    return count


ll = LinkedList()
ll.generate(10, 0, 99)
print(ll)
kth_to_last(ll, 3)

它可以很好地在列表中计数，但是对于第一个定义，我无法让它在链接列表中移动（它根本不会打印“hi”）。在

我计划做一些我已经注释过的事情（它们也定义了“tail”，所以我可以尝试一下），但是我很困惑为什么我可以在“count_length”内很好地浏览列表，但是我似乎不能在“kth_to_last”内完成它？在

编辑：为了澄清，如果我打印下一个值在“kth_to_last”内，它的值为“None”

编辑2：

如果我把“count_length”注释掉，下一个就可以了。有人能解释一下为什么调用这个函数会改变下一步。它把我困在名单的末尾了吗？在

我的代码：

^{pr2}$

这张单子印得很好

Answer 1

您应该执行val = val.next而不是val.next = val.next.next。这样，当您调用count_length时，列表将被截断为一个元素。因为您在kth_to_last的顶部做count_length，所以当您开始遍历列表时（您的'hi'就在这里），列表已经被缩减为一个节点。在

记住，linked list是一个结构，其中每个节点的next属性是指向下一个节点的指针。您的代码正在修改next的值，这将更改链接列表的结构。在

当您处理一个链表时（在count_length，或在kth_to_last）时，您要做的是依次指向每个节点。您没有尝试修改节点本身，因此不会分配给它们的value或next属性。这样做的方法是更改指针（val）所指向的对象，而您希望它指向next的对象就是下一个节点。因此：

val = ll.head
while val is not None:
    # do something with val here
    val = val.next