Reversing Linked List In-Place

In this post, I will go through a simple algorithm for reversing a singly-linked list with space complexity of O(1), i.e., in-place.

There are two methods: one with recursive and the other with iterative. To me, it is easier to solve in recursive format first and then apply iterative afterwards.

Let's dig right in!

	class Node(object):
	def __init__(self, value, next=None):
	self.value = value
	self.next = next
	def create_linked_list(n):
	if n <= 0:
	raise Exception("n must be larger than 0")
	root = Node(0)
	node = root
	for i in range(1,n):
	node.next = Node(i)
	node = node.next
	return root
	def print_linked_list(root):
	node = root
	while node is not None:
	print node.value
	node = node.next
	print
	def reverse_recursive(root):
	# break the first link
	next = root.next
	root.next = None
	# start recursion
	return reverse_recursive_helper(root, next)
	def reverse_recursive_helper(root, next):
	"""
	moves next in front of root and calls this function
	recursively with new root and new next
	:param root: root of the current linked list
	:param next: next node in the linked list
	:return: root of the new linked list
	"""
	if next is None:
	return root
	new_next = next.next
	next.next = root
	return reverse_recursive_helper(next, new_next)
	def reverse_iterative(root):
	# break the first link
	next = root.next
	root.next = None
	while next is not None:
	new_next = next.next
	next.next = root
	root = next
	next = new_next
	return root
	def reverse_with_array(root):
	array = []
	node = root
	while node is not None:
	array.append(node)
	node = node.next
	new_root = array.pop(-1)
	node = new_root
	while len(array) > 0:
	node.next = array.pop(-1)
	node = node.next
	# break the first link
	root.next = None
	return new_root
	def reverse_with_function_stack(root):
	new_root = reverse_with_function_stack_helper(root, root.next)
	# break the first link
	root.next = None
	return new_root
	def reverse_with_function_stack_helper(current, next):
	"""
	push to the function stack until next is None
	reverse the node afterwards
	:param current: current node of the original linked list
	:param next: next node of the original linked list
	:return: root of the reversed linked list
	"""
	if next is None:
	return current
	root = reverse_with_function_stack_helper(next, next.next)
	next.next = current
	return root
	if __name__ == '__main__':
	root = create_linked_list(2)
	print_linked_list(root)
	root = reverse_recursive(root)
	print_linked_list(root)
	root = reverse_iterative(root)
	print_linked_list(root)
	root = reverse_with_array(root)
	print_linked_list(root)
	root = reverse_with_function_stack(root)
	print_linked_list(root)

view raw reverse_linked_list.py hosted with ❤ by GitHub

By the way, I claim that the recursive algorithm actually has space complexity of O(N), since it is recursively called N times, growing up the stack by O(N). With this view, quick sort no longer becomes an in-place algorithm, as it requires O(log N) recursive calls.

To see why I claim this, compare the functions reverse_with_array and reverse_with_function_with_stack(_helper). They pretty much do the same thing, except that in the first case, we create an array (a list, to be exact, but can be easily replaced by an array) whereas in the second case we simply create this array using recursive function stack. In fact, the recursive way costs more in time as well as space complexity.

In any case, these methods all do the work with quite different implementations!