How to Reverse a Linked List in Swift

3 min readNov 21, 2016

There has been a lot of discussion recently about what makes an effective technical interview and whether or not it’s fair to require candidates to understand how the code they write actually works. I’m a bit conflicted about this as well. But the truth is that many of the best companies to work for still ask data structure and algorithms questions, so it’s probably worth taking some time to learn some of the questions that typically come up.

In this post I wanted to discuss one of the most popular questions that come up in technical interviews: how to reverse a linked list. I will be using Swift 3 to write the code.

Linked lists are frequently used in interviews because they are easy to understand — and more importantly — easy to code. If you’ve never encountered a linked list before, you might think of them like an array, but with a bunch of additional restrictions. For example, while it’s efficient to prepend elements to a linked list, it’s much more difficult to append a new element to the end. It’s also impossible to randomly index into a linked list.

Even with these restrictions, linked lists make up the backbone of many functional languages. I’m actually surprised that Swift has yet to receive a native implementation of this important data structure.

A linked list can be defined as either: 1) an empty list, or 2) a head element followed by a tail which is itself a linked list. This definition in terms of alternatives makes an enum the natural way to implement a linked list in Swift.

public enum LinkedList<Element> {
  case empty
  indirect case list(Element, LinkedList<Element>)
}

And that’s all it takes to develop a perfectly functional linked list data structure in Swift!

Now that we have the data structure defined, it’s time to write a function to reverse a given linked list.

The function we will write will actually just set up the initial state and then delegate to a helper function to actually reverse the list. The helper function will take two arguments: the first is what’s left of the list that is being reversed, the second is the newly reversed list that is being built up. The helper just needs to pattern match against the input string. If it’s not empty, then it can pull off the head, add the head to the new list, and then recursively call itself with the tail of the input list and the new reversed list. If the input list is empty, then the list has been fully reversed and we can return the fully reversed list.

public func reversed() -> LinkedList<Element> {
  func reversed(input: LinkedList<Element>,
        output: LinkedList<Element>) -> LinkedList<Element> {
    switch input {
    case .empty:
      return output
    case let .list(head, tail):
      return reversed(input: tail, output: .list(head, output))
    }
  }
  return reversed(input: self, output: .empty)
}

Less than a dozen lines of code later, we can now reverse a linked list.

Now let’s write a little test to see if the code can actually do what we promised. Here is some code that will build up a linked list with the numbers 1 through 4, reverse it, and then use pattern matching to make sure the list was properly reversed.

let foo = LinkedList.list(1, .list(2, .list(3, .list(4, .empty))))
let oof = foo.reversed()switch oof {
case .list(4, .list(3, .list(2, .list(1, .empty)))):
  print("Reversed!")
default:
  print("Oops.")
}

You have now been able to create a data structure to represent a linked list, written a function to reverse a linked list, and demonstrated some knowledge of advanced Swift features along the way.

How to Reverse a Linked List in Swift

Written by Robert Cottrell