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?
reverse(Node)
, to declare the local variableNode next
in the body of thewhile
loop, because you actually only need two pointers outside the loop. \$\endgroup\$