Reversing a Linked List (Important Interview Question)

To reverse a singly linked list in place, keep three pointers—prev, cur, and next—and flip each cur->next to point backward. When cur becomes NULL, prev is the new head. This uses O(n) time and O(1) extra space (no new nodes).

C program (iterative, return new `head`)

The demo builds 10 20 30 with insert_begin (same pattern as insert at beginning), prints, calls reverse_list, then prints again. Use head = reverse_list(head); because the old head becomes the tail.

Always save cur->next in next before overwriting cur->next, or you lose the rest of the list.
Empty list (head == NULL) and one-node lists are handled by the same loop.

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node *next;
};

struct Node *insert_begin(struct Node *head, int data)
{
    struct Node *newNode = malloc(sizeof(struct Node));
    if (newNode == NULL)
        return head;

    newNode->data = data;
    newNode->next = head;
    return newNode;
}

struct Node *reverse_list(struct Node *head)
{
    struct Node *prev = NULL;
    struct Node *cur = head;

    while (cur != NULL) {
        struct Node *next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }

    return prev;
}

void print_list(struct Node *head)
{
    struct Node *cur = head;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

int main(void)
{
    struct Node *head = NULL;

    head = insert_begin(head, 30);
    head = insert_begin(head, 20);
    head = insert_begin(head, 10);

    print_list(head);   /* 10 20 30 */

    head = reverse_list(head);

    print_list(head);   /* 30 20 10 */

    return 0;
}

Program output

10 20 30
30 20 10

Overall program flow

Step	Operation	`head` / new head	List state (values)
1	`head = NULL`	`NULL`	Empty list
2	`head = insert_begin(head, 30)`	`0x1000`	`30`
3	`head = insert_begin(head, 20)`	`0x2000`	`20 30`
4	`head = insert_begin(head, 10)`	`0x3000`	`10 20 30`
5	`print_list(head)`	`0x3000`	Output line: `10 20 30`
6	`head = reverse_list(head)`	Return `0x1000` (old tail)	Logical order `30 20 10`
7	`print_list(head)`	`0x1000`	Output line: `30 20 10`

Each `while` iteration inside `reverse_list`

Starting list: head is 0x3000 and forward links are 0x3000 → 0x2000 → 0x1000 → NULL.

Iteration 1 (cur at 0x3000, data 10)

Step	Operation	Result
1	`next = cur->next`	`next = 0x2000`
2	`cur->next = prev`	`0x3000->next = NULL` (first node is now detached forward)
3	`prev = cur`; `cur = next`	`prev = 0x3000`, `cur = 0x2000`

After iteration 1, reversed prefix is 10 alone; remainder still 20 → 30.

Iteration 2 (cur at 0x2000, data 20)

Step	Operation	Result
1	`next = cur->next`	`next = 0x1000`
2	`cur->next = prev`	`0x2000->next = 0x3000` (points back to `10`)
3	`prev = cur`; `cur = next`	`prev = 0x2000`, `cur = 0x1000`

After iteration 2: reversed prefix 20 → 10; cur at tail 30.

Iteration 3 (cur at 0x1000, data 30)

Step	Operation	Result
1	`next = cur->next`	`next = NULL`
2	`cur->next = prev`	`0x1000->next = 0x2000`
3	`prev = cur`; `cur = next`	`prev = 0x1000`, `cur = NULL` → loop ends

Return prev (0x1000) as the new head.

Memory layout (example addresses)

Before reverse_list (forward links)

Address	Node	`data`	`next` (before)
`0x3000`	head	10	`0x2000`
`0x2000`	—	20	`0x1000`
`0x1000`	tail	30	`NULL`

After reverse_list (backward links along the new path)

Address	Node	`data`	`next` (after)
`0x1000`	new head	30	`0x2000`
`0x2000`	—	20	`0x3000`
`0x3000`	new tail	10	`NULL`

Visual representation

Before reverse (same shape as after three insert_begin calls):

head (0x3000)
   │
   ▼
┌──────────────┐    ┌──────────────┐    ┌──────────────┐
│ data: 10     │    │ data: 20     │    │ data: 30     │
│ next: 0x2000 ┼───→│ next: 0x1000 ┼───→│ next: NULL   │
└──────────────┘    └──────────────┘    └──────────────┘

After reverse_list (new head at old tail):

head (0x1000)
   │
   ▼
┌──────────────┐    ┌──────────────┐    ┌──────────────┐
│ data: 30     │    │ data: 20     │    │ data: 10     │
│ next: 0x2000 ┼───→│ next: 0x3000 ┼───→│ next: NULL   │
└──────────────┘    └──────────────┘    └──────────────┘

Detailed step-by-step: iteration 2 of `reverse_list`

Middle iteration: cur is 0x2000 (20), prev is 0x3000 (10 already reversed).

Line	Code	Before	After
1	`struct Node *next = cur->next;`	`cur = 0x2000`	`next = 0x1000`
2	`cur->next = prev;`	`prev = 0x3000`	`0x2000->next = 0x3000`
3	`prev = cur;`	—	`prev = 0x2000`
4	`cur = next;`	—	`cur = 0x1000`

Complexity summary

Operation	Time	Extra space
`reverse_list` (iterative)	`O(n)`	`O(1)` (pointer variables only)
`insert_begin` (build demo list)	`O(1)` per call	`O(1)` per new node
`print_list`	`O(n)`	`O(1)`
Whole program (build + print + reverse + print)	`O(n)`	`O(n)` nodes stored in the list

The key takeaway is that iterative reversal runs in one pass with constant extra space—a classic interview pattern. A recursive solution reverses the rest first then rewires the head, but uses O(n) call stack space.

Alternative: recursion reverse_list_r(head) that returns the new head of the reversed list and fixes each link on the unwind; or use a stack of nodes for explicit O(n) extra space.