CODEWITHSUNDEEP
pythondata-structureslinked-list
Dat Nguyen
Dat Nguyen

Reputation: 163

Infinite loop while reversing a linked list in Python

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?

Upvotes: 0

Views: 172

Answers (1)

fountainhead
fountainhead

Reputation: 3722

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

Upvotes: 2

Related Questions