LeetCode in Ruby (11 Part Series)
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.
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
n3 to point to
n2.next.next = n2. Following this logic, we can come out with the above code.