How do you reverse a singly linked list?
Short answer: Walk the list once with three pointers (previous, current, next) and point each node's next back to the previous node. The old tail becomes the new head. O(n) time and O(1) extra memory.
#include <stdio.h>
#include <stddef.h>
struct node { int val; struct node *next; };
struct node *reverse(struct node *head)
{
struct node *prev = NULL;
while (head) {
struct node *next = head->next; /* remember the rest */
head->next = prev; /* reverse this link */
prev = head; /* advance */
head = next;
}
return prev; /* new head */
}
struct node *reverse_rec(struct node *head) /* recursive: O(n) stack, avoid in firmware */
{
if (!head || !head->next) return head;
struct node *rest = reverse_rec(head->next);
head->next->next = head;
head->next = NULL;
return rest;
}
int main(void)
{
struct node n[4] = { {1, &n[1]}, {2, &n[2]}, {3, &n[3]}, {4, NULL} };
struct node *h = reverse(&n[0]);
for (; h; h = h->next) printf("%d ", h->val); /* 4 3 2 1 */
printf("\n");
h = reverse_rec(&n[3]);
for (; h; h = h->next) printf("%d ", h->val); /* 1 2 3 4 */
printf("\n");
return 0;
}
Why iterative in embedded code: recursion uses one stack frame per node, so a 10,000-node list could overflow a 2 KB task stack; the iterative version has constant, predictable stack use.
Follow-ups: reverse in groups of k, reverse only positions m to n, check whether a list is a palindrome (find the middle, reverse the second half, compare, restore), and reverse a doubly linked list (swap next and prev in each node).