Reversing a linked list in python

Question

I am asked to reverse a which takes head as parameter where as head is a linked list e.g.: 1 -> 2 -> 3 which was returned from a function already defined I tried to implement the function reverse_linked_list in this way:

def reverse_linked_list(head):
    temp = head
    head = None
    temp1 = temp.next
    temp2 = temp1.next
    temp1.next = None
    temp2.next = temp1
    temp1.next = temp
    return temp2

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

    def to_linked_list(plist):
    head = None
    prev = None
    for element in plist:
        node = Node(element)
        if not head:
            head = node
        else:
            prev.next = node
        prev = node
    return head

    def from_linked_list(head):
    result = []
    counter = 0
    while head and counter < 100: # tests don't use more than 100 nodes, so bail if you loop 100 times.
        result.append(head.value)
        head = head.next
        counter += 1
    return result

    def check_reversal(input):
        head = to_linked_list(input)
        result = reverse_linked_list(head)
        assert list(reversed(input)) == from_linked_list(result)

It is called in this way: check_reversal([1,2,3]). The function I have written for reversing the list is giving [3,2,1,2,1,2,1,2,1] and works only for a list of length 3. How can I generalize it for a list of length n?

Answer 1

The accepted answer doesn't make any sense to me, since it refers to a bunch of stuff that doesn't seem to exist (number, node, len as a number rather than a function). Since the homework assignment this was for is probably long past, I'll post what I think is the most effective code.

This is for doing a destructive reversal, where you modify the existing list nodes:

def reverse_list(head):
    new_head = None
    while head:
        head.next, head, new_head = new_head, head.next, head # look Ma, no temp vars!
    return new_head

A less fancy implementation of the function would use one temporary variable and several assignment statements, which may be a bit easier to understand:

def reverse_list(head):
    new_head = None  # this is where we build the reversed list (reusing the existing nodes)
    while head:
        temp = head  # temp is a reference to a node we're moving from one list to the other
        head = temp.next  # the first two assignments pop the node off the front of the list
        temp.next = new_head  # the next two make it the new head of the reversed list
        new_head = temp
    return new_head

An alternative design would be to create an entirely new list without changing the old one. This would be more appropriate if you want to treat the list nodes as immutable objects:

class Node(object):
    def __init__(self, value, next=None): # if we're considering Nodes to be immutable
        self.value = value                # we need to set all their attributes up
        self.next = next                  # front, since we can't change them later

def reverse_list_nondestructive(head):
    new_head = None
    while head:
        new_head = Node(head.value, new_head)
        head = head.next
    return new_head

Answer 2

I found blckknght's answer useful and it's certainly correct, but I struggled to understand what was actually happening, due mainly to Python's syntax allowing two variables to be swapped on one line. I also found the variable names a little confusing.

In this example I use previous, current, tmp.

def reverse(head):
    current = head
    previous = None

    while current:
        tmp = current.next
        current.next = previous   # None, first time round.
        previous = current        # Used in the next iteration.
        current = tmp             # Move to next node.

    head = previous

Taking a singly linked list with 3 nodes (head = n1, tail = n3) as an example.

n1 -> n2 -> n3

Before entering the while loop for the first time, previous is initialized to None because there is no node before the head (n1).

I found it useful to imagine the variables previous, current, tmp 'moving along' the linked list, always in that order.

First iteration

previous = None

[n1] -> [n2] -> [n3] current tmp current.next = previous

Second iteration

[n1] -> [n2] -> [n3] previous current tmp current.next = previous

Third iteration

# next is None

[n1] -> [n2] -> [n3] previous current current.next = previous

Since the while loop exits when current == None the new head of the list must be set to previous which is the last node we visited.

Edited

Adding a full working example in Python (with comments and useful str representations). I'm using tmp rather than next because next is a keyword. However I happen to think it's a better name and makes the algorithm clearer.

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

    def __str__(self):
        return str(self.value)

    def set_next(self, value):
        self.next = Node(value)
        return self.next


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

    def __str__(self):
        values = []
        current = self.head
        while current:
            values.append(str(current))
            current = current.next

        return ' -> '.join(values)

    def reverse(self):
        previous = None
        current = self.head

        while current.next:
            # Remember `next`, we'll need it later.
            tmp = current.next
            # Reverse the direction of two items.
            current.next = previous
            # Move along the list.
            previous = current
            current = tmp

        # The loop exited ahead of the last item because it has no
        # `next` node. Fix that here.
        current.next = previous

        # Don't forget to update the `LinkedList`.
        self.head = current


if __name__ == "__main__":

    head = Node('a')
    head.set_next('b').set_next('c').set_next('d').set_next('e')

    ll = LinkedList(head)
    print(ll)
    ll.revevse()
    print(ll)

Results

a -> b -> c -> d -> e
e -> d -> c -> b -> a