← All problems · Data Structures
Reverse a Singly Linked List
Given the head of a singly linked list, reverse it in place and return the new head. Use O(1) extra memory and no recursion.
Write your code on the right and press Run (or Ctrl + Enter). Hidden tests check your functions and print the result below the editor.
Keep three pointers: the previous node, the current node and the next node (saved before you overwrite current->next).
#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;
head->next = prev;
prev = head;
head = next;
}
return prev;
}
Each step detaches the current node and pushes it onto the front of the reversed list held in prev. O(n) time, O(1) space. A recursive solution is shorter but uses O(n) stack, which is unacceptable on a small MCU stack for long lists.
Follow-ups: reverse in groups of k; reverse a doubly linked list (swap next and prev in each node); detect a cycle first.
solution.c
OutputPress Run to compile and test your code.
Show the hidden tests
/* ---- tests ---- */
static int fails;
#define CHECK(c) do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); fails++; } } while (0)
int main(void)
{
struct node n[5];
for (int i = 0; i < 5; i++) { n[i].val = i; n[i].next = (i < 4) ? &n[i + 1] : NULL; }
struct node *h = reverse(&n[0]);
int expect = 4, count = 0;
for (struct node *p = h; p; p = p->next, expect--, count++) CHECK(p->val == expect);
CHECK(count == 5);
CHECK(reverse(NULL) == NULL);
struct node one = { 9, NULL };
CHECK(reverse(&one) == &one && one.next == NULL);
puts(fails ? "Some tests failed" : "All tests passed");
return fails != 0;
}