Python: Перемещение через связанный список «рядом»

Question

Я работаю через Крекинг Coding Интервью 6-е изд, и я уверен в их определении «следующий»

Их код, определяющий «Linked List» можно найти here. Я пытаюсь выполнить второе упражнение, которое должно найти kth из конечного элемента случайного связанного списка.

Мой код:

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) 

Он рассчитывает через список просто отлично, но для первого определения, я не могу заставить его двигаться через связанный список (он не будет печатать «привет» в все).

Я планирую сделать что-то вроде того, что я прокомментировал (у них также есть «хвост», поэтому я могу попробовать это), но я смущен, почему я могу перемещаться по списку, просто отлично в пределах «count_length», но то я не могу переместиться через него в «kth_to_last»?

Edit: Для того, чтобы уточнить, если я печатаю val.next в 'kth_to_last' имеет значение 'None'

edit2:

Если я закомментировать "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. Поскольку вы делаете count_length в верхней части kth_to_last, к тому времени, когда вы обойдете свой список (где находится ваш '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