Reverse singly linked list

Question

Description:

Given a linked list reverse it and return the new head.

Code:

class Main {
  static class Node {
    public int data;
    public Node next;

    Node(int data) {
      this(data, null);
    }

    Node(int data, Node next) {
      this.data = data;
      this.next = next;
    }

    // Just a helper method, not optimised
    Node append(int data) {
      Node newNode = new Node(data, null);
      Node current = this;

      while (current.next != null) {
        current = current.next;
      }
      current.next = newNode;
      return this;
    }
  }
  // 10 -> 20 -> 30
  // 10    20 -> 30
  // 10 <- 20 -> 30
  //       c     n     
  // 10 <- 20 <- 30
  public static Node reverse(Node head) {
    if (head == null || head.next == null) {
      return head;
    }

    Node prev = null;
    Node curr = head;
    Node next = null;

    while (curr != null) {
      next = curr.next;
      curr.next = prev;
      prev = curr;
      curr = next;
    }

    return prev;
  }

  public static void main(String[] args) {
    Node head = new Node(10)
        .append(20)
        .append(30)
        .append(40);

    Node newHead = reverse(head);
    System.out.println(newHead); // 40 30 20 10
  }
}

Question:

The idea is quite simple i.e. we need to go one by one and we need to reverse the link, for this we need three pointers but I really struggled to put the idea into code. I know that understanding about invariants can help to write code in a more robust way. How can I help form invariants in this situation to improve the logic?

Answer 1

I can't find any very useful invariant but sum of length of list should be constant. So we can make following assertion:

static int length(Node node) {
    int result = 0;
    while (node != null) {
        result++;
        node = node.next;
    }
    return result;
}

public static Node reverse(Node head) {
    if (head == null || head.next == null) {
        return head;
    }

    int totalLength = length(head);

    Node prev = null;
    Node curr = head;
    Node next = null;


    while (curr != null) {
        assert length(prev) + length(curr) == totalLength;
        next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    assert length(prev) + length(curr) == totalLength;

    return prev;
}

It is a bit of a stretch but we can make it easier to understand why invariant is preserved by showing that single node is moved from one list to another:

static class Node {

    // rest of class without changes

    @Override
    public String toString() {
        return  data + " -> " + next;
    }


}

static class List {
    Node head;
    int size() {
        return length(head);
    }

    Node removeFist() {
        Node oldHead = head;
        head = head.next;
        return oldHead;
    }

    boolean isEmpty() {
        return head == null;
    }

    void prepend(Node newHead) {
        newHead.next = head;
        head = newHead;
    }

    static List of(Node node) {
        List list = new List();
        list.head = node;
        return list;
    }
}

static int length(Node node) {
    int result = 0;
    while (node != null) {
        result++;
        node = node.next;
    }
    return result;
}

public static Node reverse(Node head) {
    if (head == null || head.next == null) {
        return head;
    }

    List reversed = List.of(null);
    List input = List.of(head);
    final int totalSize = input.size();

    while (!input.isEmpty()) {
        assert reversed.size() + input.size() == totalSize;
        reversed.prepend(input.removeFist());
    }
    assert reversed.size() + input.size() == totalSize;

    return reversed.head;
}

Sadly I wouldn't call that improvement. Maybe it would made more sense if List class I added also contained Node tail.