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 }