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 current.next next_node = current.next # reverse the 'next' pointer current.next = previous # step forward in the list previous = current current = next_node end return previous end