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());
  }
}

Software Engineering at Cxense

A year ago I wrote [a post](http://s-j.github.io/ten-things-i-wish-i-knew-before-starting-on-a-phd/) about the things I have learned duri...… Continue reading

Having fun with Scikit-Learn

Published on December 01, 2016

A few thoughts about Spark

Published on November 21, 2016