loading...

LeetCode in Ruby: 206 Reverse Linked List

algobot76 profile image Kaitian Xie Updated on ・1 min read

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)

Discussion

pic
Editor guide