Infinite loop while reversing a linked list in Python

Question

So I have this code

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

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

  def prepend(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node
    self.length += 1

  def print_list(self):
    if self.head == None:
      print('Empty')
    else:
      currentNode = self.head
      while currentNode != None:
        print(currentNode.data, end = ' ')
        currentNode = currentNode.next

  def reverse(self):
    first = self.head
    second = first.next
    while second:
        temp = second.next
        second.next = first
        first = second
        second = temp

I prepend and then have a list of [8,7,11,6,5,10]. When I try to use the reverse function and try to print out I get infinite loop of 8 and 7. I'm not sure why. I thought the first already points to the self.head so that when it gets changed, the self.head gets changed as well. But its not the case. Could someone please help me with this?

What is the first = second part intended to do? And didn't you intend to do something with first.next? — Karl Knechtel
– Karl Knechtel, Commented Nov 25, 2020 at 6:24
The first = second part is intended to reassign the object. Like for exp, when first = 8,7,11,6,5,10 then second.next would be: 8, 7,11,6,5,10 then first will be reassigned to be 7,8,7,11,6,5,10. It goes on until all the data property of the class are in the reverse position — Dat Nguyen
– Dat Nguyen, Commented Nov 25, 2020 at 6:40
Try drawing a diagram on paper to keep track of the process. Make sure you understand how names work in Python. — Karl Knechtel
– Karl Knechtel, Commented Nov 25, 2020 at 8:35
Thanks @KarlKnechtel. Now I figure that second node is pointing towards the first node which creates infinite loop of self.head, which could be fixed by assigning self.head = first after the loop — Dat Nguyen
– Dat Nguyen, Commented Nov 29, 2020 at 5:43

fountainhead · Accepted Answer · 2020-11-25 09:08:43Z

Your reverse method is focussing on only the first two elements, and setting up cyclic references between them.

Here's the modified reverse() method, that works. (Note that the reverse() method contains an enclosed helper function called rev_(), which recurses through the linked list):

def reverse (self):          #------------MODIFIED--------------
    def rev_ (head):
        rest = head.next
        if rest is None:
            return head
        else:
            reversed_rest = rev_(rest)
            rest.next = head
            head.next = None
            return reversed_rest
        if self.head is not None:
            self.head = rev_(self.head)

Testing it out:

my_list = LinkedList()
my_list.print_list()
print()
my_list.reverse()
my_list.print_list()
print()
my_list.prepend(21)
my_list.print_list()
print()
my_list.reverse()
my_list.print_list()
print()
my_list.prepend(22)
my_list.prepend(23)
my_list.print_list()
print()
my_list.reverse()
my_list.print_list()

Output:

Empty

Empty

21 
21 
23 22 21 
21 22 23

Collectives™ on Stack Overflow

Infinite loop while reversing a linked list in Python

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related