Python:Moving通过链表'next'

Question

我正在研究破解编码面试第 6 版，但不确定他们对 'next'

的定义

他们的代码定义 "Linked List" 可以在 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' 所以我可能会尝试一下），但我很困惑为什么我可以在 [= 内很好地浏览列表40=] 但后来我似乎无法在 'kth_to_last'?

内通过它

编辑：澄清一下，如果我在 'kth_to_last' 中打印 val.next，它的值为 'None'

编辑2：

如果我注释掉 "count_length," 下一步就可以了。有人可以向我解释为什么接下来调用此函数会发生变化。它让我停留在列表末尾了吗？

我的代码：

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

    # Start at head
    val = ll.head
    while val.next != None:
        print val.next
        val = val.next

这会很好地打印列表

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）指向的东西，你希望它指向的下一个是下一个节点。因此：

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

Python:Moving通过链表'next'

Python:Moving through linked list 'next'

python

linked-list

singly-linked-list