</>EmbeddedInterview
← All problems · Data Structures

Reverse a Singly Linked List

Easy

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;
}