Python:Moving through linked list 'next'

Question

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

wildwilhelm · Accepted Answer · 2016-12-01 17:28:02Z

2

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

edited Dec 1, 2016 at 17:28

answered Dec 1, 2016 at 17:21

wildwilhelm

5,0391 gold badge22 silver badges24 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Monica Over a year ago

Thank you @wildwilhelm, that makes sense, I will fix that.

Monica Over a year ago

So the issue appears to be with my calling of "count_length" because if I comment it out then val_next is fine. Why does counting the length alter the ll?

Monica Over a year ago

Thank you @wildwilhelm, I just saw your full comment--that makes complete sense. Thank you!

Collectives™ on Stack Overflow

Python:Moving through linked list 'next'

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related