Monica Monica - 4 days ago 5
Python Question

Python:Moving through linked list 'next'

I'm working through Cracking the Coding Interview 6th ed and am unsure of their definition of 'next'

Their code defining "Linked List" can be found here. I'm trying out the second exercise, which is to find the kth from the end element of a random linked list.

My code:

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)


It's counting through the list just fine, but for the first definition, I can't get it to move through the linked list (it won't print 'hi' at all).

I plan to do something like I have commented out (they also have 'tail' defined so I might try that out), but I'm confused why I can move through the list just fine within 'count_length,' but then I can't seem to move through it within 'kth_to_last'?

Edit: To clarify, if I print val.next within 'kth_to_last' it has a value of 'None'

Edit2:

If I comment out the "count_length," the next proceeds just fine. Could someone explain to me why calling this function alters next. Has it stuck me at the end of the list?

My code:

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


This prints the list just fine

Answer

You should do val = val.next instead of val.next = val.next.next. The way you're doing it, the list will be truncated to a single element when you call count_length. Because you do count_length at the top of kth_to_last, by the time you get around to walking your list (where your 'hi' is), the list has already been reduced to a single node.

Remember, a linked list is a structure where each node's next property is a pointer to the next node. Your code is modifying the value of next, which is changing the structure of your linked list.

When you process a linked list (in count_length, or in kth_to_last), what you want to do is point yourself at each node in turn. You're not trying to modify the nodes themselves, so you won't assign to their value or next attributes. The way to do this is to change what your pointer (val) is pointing at, and the thing that you want it to point at next is the next node along. Therefore:

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