Reverse Linked List

Reverse a linked list.

One way to implement this is with recursion. For n nodes, the reverse function is called n times, once from the caller and n-1 times recursively, making the runtime O(n).

func reverse(node: Node?) -> Node? {
  if (node == nil || node?.next == nil) {
    return node
  }
  
  let head = reverse(node: node?.next)
  
  node?.next?.next = node
  node?.next = nil

  return head
}

Another way to reverse a list is iteratively. After some setup in constant time, the loop runs n-1 times, making the runtime O(n).

func reverse(node: Node?) -> Node? {
  var prev = node
  var cur = node?.next
  var next = node?.next?.next
  node?.next = nil
  
  while cur != nil {
    if cur?.next == nil {
      node = cur
      cur?.next = prev
      cur = nil
    }
    else {
      cur?.next = prev
      prev = cur
      cur = next
      next = next?.next
    }
  }

  return node
}