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)

# 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):
count = 1
while val.next != None:
count += 1
val.next = val.next.next
return count

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)
"""

while val.next != None:
print val.next
val = val.next
``````

This prints the list just fine

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
``````
Source (Stackoverflow)