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?

• Solomon Ucko: Is this working code? If so, you should probably make it clearer.
• CodeYogi: @SolomonUcko yes, it works like a charm :)
• Stingy: What exactly do you mean by using loop invariants? The code looks fine to me, the only thing I can think of to improve it would be, in the method reverse(Node), to declare the local variable Node next in the body of the while loop, because you actually only need two pointers outside the loop.
• CodeYogi: @Stingy it looks fine because I had to do a lot of trial and error.

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.