Linked List reversal algorithm not working

user_18378560 0
Viewed 51

I'm trying to write a simple function that reverses a linked list in Python:

def reverse(head):
    prev = None
    nxt = head.next
    head.next = prev
    while nxt:
        prev = head
        head = nxt
        head.next = prev
        nxt = nxt.next
    return head

The logic seemed fine when I thought through it.: First move prev to head, then shuffle head forward so it points to the same node as nxt, before setting head.next to where it was. Finally moving nxt forward by one. Iterate until nxt reaches the end of the list.

However when I tried to reverse a linked list 0->1->2->3->4->5 with the following code:

def traverse(head):
    while head:
        print(head.val)
        head = head.next

it repeatedly printed 0 and 1 endlessly.

data-structures linked-list algorithm python
2 Answers

In the while-loop:

head = nxt   # head and nxt now refer to the same node
head.next = prev   # head.next now points to previous node but nxt.next does as well
nxt = nxt.next   # this is same as: nxt = head.next  therefore same as: nxt = prev
user_9873580

As Michael pointed out, your code makes first and the second element in the linked list to point to each other.

The fix is pretty simple, here is what I did:

def reverse(head):
    nxt = head.next
    head.next = None
    while nxt:
        temp1 = nxt.next
        temp2 = head
        head = nxt 
        nxt.next = temp2
        nxt = temp1

This code initially initially does the same thing as yours. The while loop however, uses 2 temporary variables temp1 and temp2 to hold the addresses of the variables surrounding nxt (on either sides). This prevents the conflict that happened in your code.

Hope this helps! Cheers!

user_167279920
Related