I am looking to do it with Python. And I don't want to just print it in reverse, but actually reverse the given nodes. I have seen it done in other languages but had trouble finding an example in Python.
I'm trying to do it in one function, but if a helper function was needed then so be it.
def reverse (item, tail = None):
next = item.next
item.next = tail
if next is None:
return item
else:
return reverse(next, item)
Using such a simple linked list implementation:
class LinkedList:
def __init__ (self, value, next = None):
self.value = value
self.next = next
def __repr__ (self):
return 'LinkedList({}, {})'.format(self.value, repr(self.next))
Example:
>>> a = LinkedList(1, LinkedList(2, LinkedList(3, LinkedList(4))))
>>> a
LinkedList(1, LinkedList(2, LinkedList(3, LinkedList(4, None))))
>>> b = reverse(a)
>>> b
LinkedList(4, LinkedList(3, LinkedList(2, LinkedList(1, None))))
>>> a # note that there is a new head pointer now
LinkedList(1, None)
I have created a simple implementation of linked list with a reverse method that uses recursion.
class Node(object):
def __init__(self,initdata):
self.data = initdata
self.next = None
class LinkedList(object):
def __init__(self):
self.head = None
def isEmpty(self):
return self.head == None
def add(self,data): #this method adds node at head
temp = Node(data)
temp.setNext(self.head)
self.head = temp
def traverse(self):
current = self.head
while current:
if current.getNext():
print(current.data,end="->")
else:
print(current.data)
current = current.getNext()
def reverse(self,item):
if item.next == None:
self.head = item
return
self.reverse(item.next)
temp = item.next
temp.next = item
item.next = None
def main():
mylist = LinkedList()
mylist.add(15)
mylist.add(20)
mylist.add(25)
mylist.add(30)
mylist.traverse()
mylist.reverse(mylist.head)
mylist.traverse()
print(mylist.head.data)
if __name__ == "__main__":
main()
Output:
Before:
30->25->20->15
After:
15->20->25->30
Another way to do it with recursion:
def reverse(head):
# Empty list is always None
if not head:
return None
# List of length 1 is already reversed
if not head.get_next():
return head
next = head.get_next()
head.set_next(None)
rest = reverse(next)
next.set_next(head)
return rest
After seeking to thoroughly understand how to reverse a linked list in python using both iterative and recursive methods, and working on an adequate refactoring, I coded this. Many links that I studied seemed slightly unclear or had unnecessary steps. If I have not arrived at the bare minimum / clear steps, I think these are at least close. I felt it best to not include the output, but it will run as is and produce output (python 2.7 and easy to modify for 3.x).
class Node:
def __init__(self,val):
self.val = val
self.next = None # the pointer initially points to nothing
def traverse(self):
# start from the head node
node = self
while node != None:
# access the node value
out_string = 'val = %d, loc = %s, next = %s'
print out_string % (node.val, node, node.next)
# move on to the next node
node = node.next
def reverse_iteratively(self):
previous = None
current = None
head = self
while head:
# before reverse
previous = current
current = head
head = head.next
# reverse the link
current.next = previous
def reverse_recursively(self, node, pre=None):
if node.next != None:
self.reverse_recursively(node.next, pre=node)
node.next = pre
### Operation Section
node0 = Node(0)
node1 = Node(7); node0.next = node1
node2 = Node(14); node1.next = node2
node3 = Node(21); node2.next = node3
node4 = Node(28); node3.next = node4
node5 = Node(35); node4.next = node5
node6 = Node(42); node5.next = node6
node7 = Node(49); node6.next = node7
node8 = Node(56); node7.next = node8
node9 = Node(63); node8.next = node9
print "Forward linked:"
node0.traverse()
node0.reverse_recursively(node0)
print "Reverse linked:"
node9.traverse()
Slight modification to @Rajat Bhatt implementation. Difference is below code can be executed as a separate function outside of linked list class.
print '\n-- Initialize --'
lst = LinkedList(10) # 10 --> *
print '\n-- Insert --'
lst.append(20) # 10 --> 20 --> *
lst.append(30) # 10 --> 20 --> 30 --> *
lst.insertAt(15, pos=1) # 10 --> 15 --> 20 --> 30 --> *
lst.insertAt(25, pos=3) # 10 --> 15 --> 20 --> 25 --> 30 --> *
lst.insertAt(2) # 2 --> 10 --> 15 --> 20 --> 25 --> 30 --> *
lst.append(100) # 2 --> 10 --> 15 --> 20 --> 25 --> 30 --> 100 --> *
lst.append(500) # 2 --> 10 --> 15 --> 20 --> 25 --> 30 --> 100 --> 500 --> *
print lst
# 2 --> 10 --> 15 --> 20 --> 25 --> 30 --> 100 --> 500 --> *
print '\n-- Reverse using Recursion --'
def revFunc(curr):
if curr.next_node is None:
lst.head = curr
return None
revFunc(curr.next_node)
curr.next_node.next_node = curr
curr.next_node = None
revFunc(lst.head)
print lst
# Head --> 500 --> 100 --> 30 --> 25 --> 20 --> 15 --> 10 --> 2 --> *
def reverse_list(self,node):
if node is None:
return //list is empty
elif node.next is None:
self.head = node // changing the head to last node after reversal
return
else:
reverse_list(node.next) //call the function recursively until the end of the list
node.next.next = node //reverse the link
node.next = None
def reverse_ll_pass(self):
temp = self.head
if temp is None:
return
return self.reverse_ll_recursive(temp,past=None)
def reverse_ll_recursive(self,curr,past):
if curr is None:
self.head = past
return self.head
else:
future = curr.next
curr.next = past
past = curr
curr = future
return self.reverse_ll_recursive(curr,past)
Very similar to poke's solution, but I prefer to have the base case first:
def reverse(head, reversed=None):
if head is None:
return reversed
new_head = head.next
head.next = reversed
new_reversed = head
return reverse(new_head, new_reversed)
Two possible ways to implement this.
First one, does not rely on a class attribute to conserve the head once you find it. It returns the pointer to the head through the recursive calls stack
def reverseList(head):
# Empty list is always None
if not head:
return None
# List of length 1 is already reversed
if not head.next:
return head
next = head.next
head.next = None
rest = reverseList(next)
next.next = head
return rest
Second solution, with a pointer to the head (a class attribute) within your class
class Solution:
head: Optional[ListNode]
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
node = head
if node == None:
return node
if node.next == None:
self.head = node
return
self.reverseList(node.next)
q = node.next
q.next = node
node.next = None
return self.head
def reverse_linkedlist(node):
if node == None or node.next == None:
return node
else:
last_node = reverse_linkedlist(node.next)
new_head = node.next
new_head.next = node
node.next = None
return last_node
