1

I am a bit new to python and I have seen the correct solutions to the reversing the linkedlist problem but I wanted to know why my solution does not work. In particular, reverse function stays inside the while loop for the code below because of "new_list.head.next=prev" line 

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, value):
        if self.head is None:
            self.head = Node(value)
            return

        node = self.head
        while node.next:
            node = node.next

        node.next = Node(value)

    def __iter__(self):
        node = self.head
        while node:
            yield node.value
            node = node.next

    def __repr__(self):
        return str([v for v in self])

def reverse(linked_list):
    new_list = LinkedList()
    if linked_list is None:
        return new_list
    node = linked_list.head
    new_list.head = node 
    while node.next:
        prev = node
        node = node.next
        new_list.head = node
        new_list.head.next = prev
    return new_list   

if __name__ == "__main__":
    a = LinkedList()
    b = [1,2,3,4,5]
    for item in b:
        a.append(item)
    print a
    c = reverse(a) 
    print c
Improve this question
2
  • You tagged with python-3.x but used old print a syntax... Commented May 17, 2019 at 22:59
  • In your while loop you are assigning prev to new_list.head.next but you should assign the previous new_list.head instead. Commented May 17, 2019 at 23:07

3 Answers 3

Reset to default
2

If you tag your question with Python3 please make sure it runs in python 3.

The reason is because you are mixing up points and creating an infinite loop. Print the value and it may help you find the bug. I am going to use the values to point out the issue.

    while node.next:
        # First node that comes in value = 1
        print(node.value) #
        prev = node # prev = 1
        node = node.next # node = 2
        new_list.head = node # You are setting the head = 2 (i.e. head = node.next)
        new_list.head.next = prev # You are setting next of head = 1 (i.e. head.next = node.next.next)
        # however this also set node.next.next = 1
        # So going into the next loop: node.value = 2 and node.next.value = 1

Because of this pointer confusion you are forever looping between your first and second node.

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

1 Comment

Thanks sorry for the python 3 confusion
2

This is how your reverse can look:

def reverse(linked_list):
    new_list = LinkedList()
    if linked_list is None:
        return new_list
    node = linked_list.head
    new_list.head = Node(node.value)
    while node.next:
        node = node.next
        prev_head = new_list.head
        new_list.head = Node(node.value)
        new_list.head.next = prev_head
    return new_list

With it I got desired output of print c: [5, 4, 3, 2, 1]

General advise: create new Node instead of assignment to node in initial list.

Improve this answer

9 Comments

It's not in the spirit of this to create new Nodes. It's supposed to be reversed in place.
But OP is creating new_list. Having two lists with the same nodes will lead to lot of bugs.
Yes, you are probably right @Sanyash — but this is normally an exercise in manipulating references, not writing production code.
Yes the problem I was given was to create new list and not in place.
If returning new list - yes. Otherwise changes to one list will be reflected to other. See my comment: stackoverflow.com/questions/56194314/…
|
1

It's a little easier to reason about this (at least to me) if you think about two references:

• One to the remaining part of the original list you haven't seen
• One to the head of the new list

At each iteration move the remaining up and set the old remaining to the head of the new list. Order is important here — as you've seen it's easy to accidentally change next on two different variables that are pointing the same node if you're not careful:

def reverse(linked_list):
    new_list = LinkedList()

    if linked_list is None:
        return new_list

    remaining = linked_list.head

    while remaining:
        prev_head = new_list.head       # the old head becomes the first link
        new_list.head = remaining       # new head becomese the first remaining
        remaining = remaining.next      # move remaing one up the chain
        new_list.head.next = prev_head  # point the new head to the previous   
    return new_list
Improve this answer

7 Comments

After doing c = reverse(a) \n a.append(6) you will have c = [5, 4, 3, 2, 1, 6]. That's why I said that not creating new Nodes is not so good idea.
Yes @Sanyash that's expected with an in-place linked list reversal. This is an old-school computer-science pointer exercise. This is the same behavior you get in other sorts of references like revising a python lists in place with reverse().
What about if we use this code? new_list = LinkedList() if linked_list.head is None: return new_list node = linked_list.head while node: old_head = new_list.head new_node = node node = node.next new_node.next = old_head new_list.head = new_node return new_list
Sorry I don't know how to put code inside comments. In the above case c and a will be different right Sanyash?
@vkaul11 if you are doing this is an assignment, this is likely what the assignment had in mind. Since it is an in-place reversal, it probably makes more sense as a method on the linked list. Then you would call list.reverse(), but you would need to change a few details. If you really want a new list, with new Nodes, there's much cleaner ways than anything in this thread.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.