Reverse a linked list

Reading time ~1 minute

I’ve been into a couple of interviews during the last two weeks. Today I got an interesting question: “reverse a single-linked list, in place”. The solution I suggested was good, but not great - “a better solution would use non-static recursion and be only two lines long”. After some thinking on the way home, I think the answer could look like this (updated version):

public class LinkedList {

  public String s;
  public LinkedList tail;

  public LinkedList(String s) {
    this.s = s;
    this.tail = null;
  }

  public LinkedList add(String s) {
    if (this.tail == null) {
      this.tail = new LinkedList(s);
    } else {
      this.tail.add(s);
    }
    return this;
  }

  public LinkedList reverse() {
    if (this.tail == null) {
      return new LinkedList(this.s);
    } else {
      return this.tail.reverse().add(this.s);
    }
  }

  @Override
  public String toString() {
    if (this.tail != null) {
      return s + " -> " + tail;
    } else {
      return s;
    }
  }

  public static void main(String[] args) {
    System.err.println(new LinkedList("s").add("i").add("m").add("o").add("n").reverse());
  }
}

Getting started with Flutter on Mac

[Flutter](https://flutter.io/) is a great Google SDK allowing effortless creation of mobile apps with native interfaceson iOS and Android...… Continue reading

On designing and running online experiments

Published on February 28, 2018

Software Engineering at Cxense

Published on April 17, 2017