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

Answer 3

Here is a way to reverse the list 'in place'. This runs in constant time O(n) and uses zero additional space.

def reverse(head):
  if not head:
    return head
  h = head
  q = None
  p = h.next
  while (p):
    h.next = q
    q = h
    h = p
    p = h.next
  h.next = q
  return h

Here's an animation to show the algorithm running.
(# symbolizes Null/None for purposes of animation)

Answer 4

Node class part borrowed from interactive python.org: http://interactivepython.org/runestone/static/pythonds/BasicDS/ImplementinganUnorderedListLinkedLists.html

I created the reversed function. All comments in the loop of reverse meant for 1st time looping. Then it continues.

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

  def setData(self,newdata):
    self.d = newdata

  def setNext(self,newnext):
    self.next = newnext

  def getData(self):
    return self.d

  def getNext(self):
    return self.next

class LinkList():
  def __init__(self):
    self.head = None

  def reverse(self):
    current = self.head   >>> set current to head(start of node)
    previous = None       >>>  no node at previous
    while current !=None: >>> While current node is not null, loop
        nextt =  current.getNext()  >>> create a pointing var to next node(will use later)
        current.setNext(previous)   >>> current node(or head node for first time loop) is set to previous(ie NULL), now we are breaking the link of the first node to second node, this is where nextt helps(coz we have pointer to next node for looping)
        previous = current  >>> just move previous(which was pointing to NULL to current node)
        current = nextt     >>> just move current(which was pointing to head to next node)

    self.head = previous   >>> after looping is done, (move the head to not current coz current has moved to next), move the head to previous which is the last node.

Answer 5

You can do the following to reverse a singly linked list (I assume your list is singly connected with each other).

First you make a class Node, and initiate a default constructor that will take the value of data in it.

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

This solution will reverse your linked list "iteratively". I am making a class called SinglyLinkedList which will have a constructor:

class SinglyLinkedList:
    def __init__(self):
        self.head = None
    

then I have written a method to reverse the list, print the length of the list, and to print the list itself:

# method to REVERSE THE LINKED LIST
def reverse_list_iterative(self):
    prev = None
    current = self.head
    following = current.next
    while (current):
        current.next = prev
        prev = current
        current = following
        if following:
            following = following.next
    self.head = prev

        
# Method to return the length of the list
def listLength(self):
    count = 0
    temp = self.head
    while (temp != None):
        temp = temp.next
        count += 1
    return count

# Method to print the list
def printList(self):
    if self.head ==  None:
        print("The list is empty")
    else:
        current_node = self.head
        while current_node:
            print(current_node.data, end = " -> ")
            current_node = current_node.next
        
        if current_node == None:
            print("End")`

After that I hard code the list, and its contents and then I link them

if __name__ == '__main__':
    sll = SinglyLinkedList()
    sll.head = Node(1)
    second = Node(2)
    third = Node(3)
    fourth = Node(4)
    fifth = Node(5)

    # Now linking the SLL
    sll.head.next = second
    second.next = third
    third.next = fourth
    fourth.next = fifth

    print("Length of the Singly Linked List is: ", sll.listLength())
    print()
    print("Linked List before reversal")
    sll.printList()
    print()
    print()
    sll.reverse_list_iterative()
    print("Linked List after reversal")
    sll.printList()

Output will be:

Length of the Singly Linked List is: 5

Linked List before reversal 1 -> 2 -> 3 -> 4 -> 5 -> End

Linked List after reversal 5 -> 4 -> 3 -> 2 -> 1 -> End

Answer 6

I tried a different approach, in place reversal of the LList. Given a list 1,2,3,4

If you successively swap nearby nodes,you'll get the solution.

len=3 (size-1)
2,1,3,4
2,3,1,4
2,3,4,1

len=2 (size-2)
3,2,4,1
3,4,2,1

len=1 (size-3)
4,3,2,1

The code below does just that. Outer for loop successively reduces the len of list to swap between. While loop swaps the data elements of the Nodes.

def Reverse(head):
    temp = head
    llSize = 0
    while temp is not None:
        llSize += 1
        temp = temp.next


    for i in xrange(llSize-1,0,-1):
        xcount = 0
        temp = head
        while (xcount != i):
            temp.data, temp.next.data = temp.next.data, temp.data
            temp = temp.next
            xcount += 1
    return head

This might not be as efficient as other solutions, but helps to see the problem in a different light. Hope you find this useful.

Answer 7

Here is the whole thing in one sheet. Contains the creation of a linked list, and code to reverse it.

Includes an example so you can just copy and paste into an idle .py file and run it.

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


def reverse(head):
    temp = head
    llSize = 0
    while temp is not None:
        llSize += 1
        temp = temp.next
    for i in xrange(llSize-1,0,-1):
        xcount = 0
        temp = head
        while (xcount != i):
            temp.value, temp.next.value = temp.next.value, temp.value
            temp = temp.next
            xcount += 1
    return head


def printnodes(n):
    b = True
    while b == True:
        try:
            print n.value
            n = n.next
        except:
            b = False

n0 = Node(1,Node(2,Node(3,Node(4,Node(5,)))))
print 'Nodes in order...'
printnodes(n0)
print '---'
print 'Nodes reversed...'
n1 = reverse(n0)
printnodes(n1)

Answer 8

def reverseLinkedList(head):

    current =  head
    previous = None
    nextNode = None

    while current:

        nextNode = current.nextNode
        current.nextNode = previous

        previous = current
        current = nextNode

    return previous

Answer 9

Most previous answers are correct but none of them had the complete code including the insert method before and and after the reverse so you could actually see the outputs and compare. That's why I'm responding to this question. The main part of the code of course is the reverse_list() method. This is in Python 3.7 by the way.

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


class LinkedList(object):

    def __incurrent__(self, head=None):
        self.head = head

    def insert(self, data):
        tmp = self.head
        self.head = Node(data)
        self.head.next = tmp

    def reverse_list(self):
        current = self.head
        prev = None

        while current :
            #create tmp to point to next
            tmp = current.next
            # set the next to point to previous
            current.next = prev
            # set the previous to point to current
            prev = current
            #set the current to point to tmp
            current = tmp
        self.head = prev


    def print(self):
        current = self.head
        while current != None:
            print(current.data,end="-")
            current = current.next
        print(" ")


lk = LinkedList()
lk.insert("a")
lk.insert("b")
lk.insert("c")

lk.print()
lk.reverse_list()
lk.print()

output:

c-b-a- 
a-b-c- 

Answer 10

Following is the generalized code to reverse a singly linked list, where head is given as function's argument:

def reverseSll(ll_head):
    # if head of the linked list is empty then nothing to reverse
    if not ll_head:
        return False
    # if only one node, reverse of one node list is the same node
    if not ll_head.next:
        return ll_head
    else:
        second = ll_head.next # get the second node of the list
        ll_head.next = None # detach head node from the rest of the list
        reversedLL = reverseSll(second) # reverse rest of the list
        second.next = ll_head # attach head node to last of the reversed list
        return reversedLL

Let me explain what I am doing here:

1) if head is null or head.next is null(only one node left in the list) return node
2) else part: take out 1st node, remove its link to rest of the list, reverse rest of the list(reverseSll(second)) and add 1st node again at last and return the list

Github link for the same

Answer 11

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


class LinkedList :

    def __init__(self):
        self.head = None
    

    def add(self, data):
        
        node = Node(data)
        if not self.head:
            self.head = node
        else:
            current = self.head
            
            while current.next != None:
                current = current.next

            current.next = node

    def printList(self):
        value = []
        if not self.head:
            print("liss is Empty")
        else:
            current = self.head
            while current:
                value.append(current.data)
                current = current.next
        print(value)
            
    # this func start reverse list from the last to first 
    def reverseLinkedList(self,node1,node2):
        if self.head == None:
            print("list Empty")
        else:
# when we reach the last of list we link head with the last element and we disconnect head with second element that will make first element in the last of the list

            if node2 == None and node1 != None:
                self.head.next = None
                self.head = node1

                return
            else:
                self.reverseLinkedList(node1.next, node2.next )
                node2.next = node1


ln = LinkedList()
ln.add(1)
ln.add(2)
ln.add(3)
ln.add(4)
ln.add(5)
ln.add(6)
ln.add(7)
ln.add(8)
ln.add(9)
ln.printList()
ln.reverseLinkedList(ln.head,ln.head.next)
print("after first reverse")
ln.printList()
# after i reverse list I add new item to the last
ln.add(0)
print("after add new element to the last of the list")
ln.printList()
print("after second reverse")
# i made second reverse to check after I add new element if my function work perfectly
ln.reverseLinkedList(ln.head,ln.head.next)
ln.printList()

Output : [1, 2, 3, 4, 5, 6, 7, 8, 9]

after first reverse

[9, 8, 7, 6, 5, 4, 3, 2, 1]

after add new element to the last of the list

[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

after second reverse

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Answer 12

Efficient way to reverse linkedlist is discussed in the below steps. Approach to reverse the linking.

1. Use a variable curr and equal it to head.
2. Use a variable prev and equal it to None.
3. Apply the loop with the condition that loop will run till curr is not None and in this condition use another variable next which is equal to curr.next. This will be used to get hold of next node. Now make curr.next = prev. In this way the head after reversing linkedlist will point to None. Now make prev = curr and curr = next

Code snippet

def reverse_linked_list(head):
    # corner case
    if head == None:
        return
    curr = head
    # reason being orginal head after reversing should point to None
    prev = None
    while curr is not None:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    # prev is returned because both curr and next will be None after reversing

    return prev

There is another way to perform the task which will take time complexity as theta(n) and space complexity as theta(n). This is a recursive solution and steps are as below

• Step 1: Apply the recursion for n -1 node from the end side. This means reverse the list leaving the first node.
• Step 2: Link the first node with all nodes obtained from step 1 in reverse order

Code

def reverse_linked_list_recursion(head):
    # corner case
    if head == None:
        return
    if head.next == None:
        return head

    rest_head = reverse_linked_list_recursion(head.next)
    rest_tail = head.next
    rest_tail.next = head
    head.next = None

    return rest_head

Answer 13

U can use mod function to get the remainder for each iteration and obviously it will help reversing the list . I think you are a student from Mission R and D

head=None   
prev=None
for i in range(len):
    node=Node(number%10)
    if not head:
        head=node
    else:
        prev.next=node
    prev=node
    number=number/10
return head