Linked Structures

Linked List

Reverse In Place

Walk a singly linked list once, rewiring each node's next to point at the previous node. Returns the new head, which is the old tail.

Algorithm

Basic Implementation

basic.sh 
#!/usr/bin/env bash
set -euo pipefail
node_value=()
node_next=()
last_idx=-1

add_node() {
	local value=$1
	local next_idx=$2
	local idx=${#node_value[@]}
	node_value[idx]=$value
	node_next[idx]=$next_idx
	last_idx=$idx
}

add_node 5 -1;   n5=$last_idx
add_node 4 "$n5"; n4=$last_idx
add_node 3 "$n4"; n3=$last_idx
add_node 2 "$n3"; n2=$last_idx
add_node 1 "$n2"; head=$last_idx

prev=-1
cursor=$head
while [ "$cursor" -ne -1 ]; do
	next_idx=${node_next[cursor]}
	node_next[cursor]=$prev
	prev=$cursor
	cursor=$next_idx
done
head=$prev
cur=$head
while [ "$cur" -ne -1 ]; do
	printf '%d -> ' "${node_value[cur]}"
	cur=${node_next[cur]}
done
printf 'null\n'

The three-pointer loop saves the forward link, flips one next pointer, then advances prev and cursor.

Step 1 - Save the first forward link

prev starts at null, cursor is node(1), and nxt saves node(2).

Initial 1 -> 2 -> 3 -> 4 -> 5 chain with prev, cursor, and nxt named.prevcursornxtnullnode(1)node(2)node(3)node(4)node(5)

Step 2 - Flip node(1)

Set node(1).next to prev, making the reversed prefix 1 -> null.

After the first flip, prev points at node(1) and cursor advances to node(2).prevcursornode(1)nullnode(2)node(3)node(4)node(5)

Step 3 - Reversed prefix reaches 3

After three flips, the prefix is 3 -> 2 -> 1 -> null and cursor is node(4).

Middle of the reverse: prefix 3 -> 2 -> 1, suffix 4 -> 5.prevcursornode(3)node(2)node(1)nullnode(4)node(5)

Step 4 - Done

When cursor reaches null, prev is the new head: 5 -> 4 -> 3 -> 2 -> 1 -> null.

Final reversed list.headnode(5)node(4)node(3)node(2)node(1)null

Complexity

  • Time: O(n)
  • Space: O(1)

Implementation notes

  • Bash: command substitution $(add_node ...) runs in a subshell, so the add_node function mutates the node_value / node_next globals directly and reports the new index through a last_idx global. The caller pattern add_node ...; n_k=$last_idx keeps the arena consistent without leaning on Bash 5 namerefs.
  • -1 is the null sentinel; the rewire loop runs while [ "$cursor" -ne -1 ].
  • The replay shows each step's cursor, prev, saved next_idx, and a one-line list view that updates as nodes flip.
three-pointer rewire Keep `prev`, `cursor`, and `next_idx` integers. At each step: save `next_idx`, flip `cursor.next = prev`, then advance `prev = cursor` and `cursor = next_idx`.
tail becomes head After the loop, `prev` is the new head. The reversed chain prints as `5 -> 4 -> 3 -> 2 -> 1 -> null`.