Description:

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) {
}

Node prev = null;
Node next = null;

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

return prev;
}

public static void main(String[] args) {
.append(20)
.append(30)
.append(40);

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?

• Is this working code? If so, you should probably make it clearer. Mar 30, 2018 at 20:59
• @SolomonUcko yes, it works like a charm :) Mar 30, 2018 at 21:00
• 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. Mar 31, 2018 at 10:18
• @Stingy it looks fine because I had to do a lot of trial and error. Mar 31, 2018 at 19:46

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) {
}

Node prev = null;
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 {
int size() {
}

Node removeFist() {
}

boolean isEmpty() {
}

}

static List of(Node node) {
List list = new List();
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) {
}

List reversed = List.of(null);

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