Iterative
def reverse_list(head)
prev = nil
curr = head
until curr.nil?
temp = curr.next
curr.next = prev
prev = curr
curr = temp
end
prev
end
The purpose of this approach is to change the next
pointer of a node to point to its previous node. Before we start looping through each node, we need the pointer prev
to store the previous node. Also, while we are iterating through the nodes, we need the temp
node so that we can swap cur
node with cur.next
node, which will be the node we process in the next iteration.
Time complexity: O(n)
Extra memory: O(1)
Recursive
def reverse_list(head)
return head if head.nil? || head.next.nil?
p = reverse_list(head.next)
head.next.next = head
head.next = nil
p
end
Although the recursive approach is as efficient as the iterative one, it is hard to figure out. Let's assume that we have a linked list n1 -> n2 -> n3 -> nill
. Assume that the last two have been reversed. i.e. n1 -> n2 -> n3 <- nill
, and you are at the n2
. You want the next
of n3
to point to n2
, i.e n2.next.next = n2
. Following this logic, we can come out with the above code.
Time complexity: O(n)
Extra memory: O(1)
Top comments (0)