Reverse a Linked List

Algorithm and Data structures have been one of my weak point for quite some time now. And after working for more than 6 years a lot of these are forgotten. Past few days have been brushing up my skills and will be documenting here.

Starting with Linked list, here's how to reverse a linked list.

Assume that we have linked list 1 → 2 → 3, we would like to change it to 1 ← 2 ← 3.

A simpler way to come up with solution is by iterative way. We can traversing the list, change the current node's next pointer to point to its previous element. Since a node does not have reference to its previous node, you must store its previous element beforehand. You also need another pointer to store the next node before changing the reference. Do not forget to return the new head reference at the end!

# Time complexity: O(n)
# Space complexity: O(1)

def reverse(head_of_list)
  current = head_of_list
  previous = nil
  next_node = nil

  # until we have 'fallen off' the end of the list
  while current

    # copy a pointer to the next element
    # before we overwrite
    next_node =

    # reverse the 'next' pointer = previous

    # step forward in the list
    previous = current
    current = next_node

  return previous
By @Aniruddha Barapatre in
Tags : #CS, #Data structures, #Linked List,

Comments !