Card 03/ 08
The In-Place Reversal Template in Python, Java and TypeScript
Four lines inside one loop, in an order that never loses the rest of the list.
The in-place reversal template is one loop of four lines, highlighted in each listing because their order is what the listing teaches: save the next node, point curr.next at prev, move prev to curr, move curr to the saved node. The function returns prev, the new head. Each listing builds 7 3 9 5 and prints it before and after.
The reversal template in three languages
class ListNode:
def __init__(self, val):
self.val = val
self.next = None
def build(values):
head = None
for val in reversed(values):
node = ListNode(val)
node.next = head
head = node
return head
def values_of(head):
values = []
while head:
values.append(head.val)
head = head.next
return values
def reverse(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
head = build([7, 3, 9, 5])
print("before:", *values_of(head))
print("after:", *values_of(reverse(head)))before: 7 3 9 5
after: 5 9 3 7import java.util.StringJoiner;
public class Reversal {
static class ListNode {
final int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
static ListNode build(int[] values) {
ListNode head = null;
for (int i = values.length - 1; i >= 0; i--) {
ListNode node = new ListNode(values[i]);
node.next = head;
head = node;
}
return head;
}
static String valuesOf(ListNode head) {
StringJoiner values = new StringJoiner(" ");
for (ListNode node = head; node != null; node = node.next) {
values.add(String.valueOf(node.val));
}
return values.toString();
}
static ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextNode = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}
return prev;
}
public static void main(String[] args) {
ListNode head = build(new int[] {7, 3, 9, 5});
System.out.println("before: " + valuesOf(head));
System.out.println("after: " + valuesOf(reverse(head)));
}
}before: 7 3 9 5
after: 5 9 3 7class ListNode {
next: ListNode | null = null;
readonly val: number;
constructor(val: number) {
this.val = val;
}
}
function build(values: number[]): ListNode | null {
let head: ListNode | null = null;
for (let i = values.length - 1; i >= 0; i--) {
const node = new ListNode(values[i]);
node.next = head;
head = node;
}
return head;
}
function valuesOf(head: ListNode | null): string {
const values: number[] = [];
for (let node = head; node !== null; node = node.next) {
values.push(node.val);
}
return values.join(" ");
}
function reverse(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
let curr = head;
while (curr !== null) {
const nextNode: ListNode | null = curr.next;
curr.next = prev;
prev = curr;
curr = nextNode;
}
return prev;
}
const head = build([7, 3, 9, 5]);
console.log("before:", valuesOf(head));
console.log("after:", valuesOf(reverse(head)));before: 7 3 9 5
after: 5 9 3 7All three print 5 9 3 7. The saved node is called next_node in Python, because next is a built-in function there, and nextNode in the other two to match. Python also allows curr.next, prev, curr = prev, curr, curr.next on one line, which works because the right side is evaluated in full before any assignment, but reordering its targets breaks it silently; the listings keep four explicit lines so that the three match line for line. TypeScript types next as ListNode | null, and an empty list, a null head, returns null from all three without entering the loop. The function is O(n) time and O(1) extra space.
← → move through sections and cards