Approach on Reversing a Linked List in Python

Question

I tried the following code to reverse a linked list and is getting an infinite loop as an error. Can you pls tell me what's wrong in this approach.

def reverse(self):
   temp  = curr = self.head         #curr refers to the next node
   prev = None
   while temp:
          curr = temp.next    #curr goes to the next node of temp           
          curr.next = temp    #curr node points to its previous node temp
          prev = temp         #prev moves to the next node
          temp = curr
   #self.head.next = None 
   self.head = prev

A.H · Accepted Answer · 2018-12-13 07:03:42Z

2

There is a logic error in your method.

At the end of the first pass of the while loop:

curr (2nd element in list)
curr.next (1st element in list)
temp = curr = (2nd element in list)

In the second pass of the while loop. You expect to reach the 3rd element using temp.next. This is wrong because:

temp.next = curr.next = (1st element in list)

Leaving you to loop infinitely between the first and second element with no exit condition.

I will leave you to figure out the proper solution for this.

(Hint: temp should be assigned to the ??? element in the 1st pass)

edited Dec 13, 2018 at 7:03

answered Dec 13, 2018 at 6:55

A.H

858 bronze badges

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

2 Comments

mouviciel Over a year ago

The secret is the loop invariant, that you point out.

Drool Over a year ago

Thanks! it helped.

Collectives™ on Stack Overflow

Approach on Reversing a Linked List in Python

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related