What is Reverse Linked List Code- Learn C Programming Online Free

🚀 Learn BLE on Linux (BlueZ) – Programming Part 1

Hands-on Bluetooth Low Energy course. Special price: ₹399

Enroll Now on Udemy →
💬 Need help or career guidance? Ask us!Contact Us →

PREV_LEC | NEXT_LEC

Reverse Linked List Code

Free C programming course: write, run and test the iterative reverse function, apply it in an embedded sensor lab, then check yourself with a quiz and interview questions.

In the last lecture you learned the idea behind reversing a list: save, flip, advance. Now we turn that idea into working code and prove it works by running it. This lecture finishes the linked list section of our free C programming course. You will write the reverse linked list in C function, trace its output, solve a small embedded C programming lab that replays sensor readings in arrival order, and close with a quiz and interview questions. It is the kind of practice a good free embedded C course should give you before a job interview.

What You Will Learn

  • How to write the iterative reverse_list() function in C
  • How to read a step-by-step trace of the pointers
  • How to test empty, single-node and multi-node lists
  • How to use reversal to turn a stack-like list into arrival order
  • How to check your code with AddressSanitizer
  • Quiz questions and interview questions on linked lists

Prerequisites

  • The previous lecture on the three-pointer reversal logic
  • Insertion, traversal and freeing a linked list

The reverse_list Function

Here is the idea in code. The four statements inside the loop are exactly the four moves from the last lecture, in the same order.

void reverse_list(struct node **head)
{
    struct node *prev = NULL;
    struct node *cur = *head;
    struct node *next;

    while (cur != NULL) {
        next = cur->next;   /* 1. save the rest */
        cur->next = prev;   /* 2. flip the arrow */
        prev = cur;         /* 3. advance prev */
        cur = next;         /* 4. advance cur */
    }
    *head = prev;           /* old last node is the new first */
}

One pass of the loop

1 Savenext remembers cur->next
2 Flipcur->next now points to prev
3 Move prevprev takes the value of cur
4 Move curcur takes the value of next

The function takes struct node **head because the head must change: the old last node becomes the first. A function that took only struct node *head could reverse the arrows but would leave the caller’s head pointing at what is now the last node.

A Complete Test Program With Trace

This program builds the list 8, 21, 34, 55, prints it, reverses it, prints it again, then reverses once more to prove that two reversals restore the original. A printf inside the loop shows each pass.

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

struct node {
    int value;
    struct node *next;
};

static struct node *make_node(int value, struct node *next)
{
    struct node *n = malloc(sizeof *n);

    if (n == NULL) {
        perror("malloc");
        exit(EXIT_FAILURE);
    }
    n->value = value;
    n->next = next;
    return n;
}

static void print_list(const char *label, const struct node *head)
{
    printf("%-8s:", label);
    for (; head != NULL; head = head->next)
        printf(" %d", head->value);
    printf("\n");
}

void reverse_list(struct node **head)
{
    struct node *prev = NULL;
    struct node *cur = *head;
    struct node *next;
    int step = 1;

    while (cur != NULL) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
        printf("step %d: prev=%d cur=%s\n", step++, prev->value,
               cur ? "next node" : "NULL");
    }
    *head = prev;
}

int main(void)
{
    struct node *head = make_node(8, make_node(21, make_node(34, make_node(55, NULL))));
    struct node *next;

    print_list("before", head);
    reverse_list(&head);
    print_list("after", head);

    reverse_list(&head);
    print_list("again", head);

    while (head != NULL) {
        next = head->next;
        free(head);
        head = next;
    }
    return 0;
}

Build and run

gcc -std=c17 -Wall -Wextra -fsanitize=address,undefined -o reverse_demo reverse_demo.c
./reverse_demo

Expected output

before  : 8 21 34 55
step 1: prev=8 cur=next node
step 2: prev=21 cur=next node
step 3: prev=34 cur=next node
step 4: prev=55 cur=NULL
after   : 55 34 21 8
step 1: prev=55 cur=next node
step 2: prev=34 cur=next node
step 3: prev=21 cur=next node
step 4: prev=8 cur=NULL
again   : 8 21 34 55

Read the trace against the table from the last lecture. After step 4, cur is NULL and prev is 55, so *head = prev makes 55 the first node. The sanitizer reported nothing, which means no leak and no invalid access.

Why reversing twice is a good test

A correct reversal is its own inverse. If the second call does not bring back the original order, some arrow was flipped wrongly. This is a cheap self-check you can add to any test.

Edge Case Checklist

InputExpectedWhy it works
NULL listhead stays NULLLoop never runs, prev is NULL
One nodeSame single nodeNode points to NULL, becomes head
Two nodes 1, 22, 1Two passes swap the arrows
Four nodesFully reversedShown in the trace

Embedded Lab: Replay ADC Readings in Order

Problem. An interrupt handler records each ADC sample by pushing it at the front of a list, because front insertion is O(1) and fast. The main loop wants to process samples oldest first. Use reversal once, then process.

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

struct reading {
    int sample;
    struct reading *next;
};

static void push_front(struct reading **head, int sample)
{
    struct reading *r = malloc(sizeof *r);

    if (r == NULL) {
        perror("malloc");
        exit(EXIT_FAILURE);
    }
    r->sample = sample;
    r->next = *head;
    *head = r;
}

static void reverse(struct reading **head)
{
    struct reading *prev = NULL, *cur = *head, *next;

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

static void show(const char *label, const struct reading *r)
{
    printf("%s:", label);
    for (; r != NULL; r = r->next)
        printf(" %d", r->sample);
    printf("\n");
}

int main(void)
{
    struct reading *head = NULL;
    int adc[] = {512, 530, 498, 505, 540};
    size_t i;

    for (i = 0; i < sizeof adc / sizeof adc[0]; i++)
        push_front(&head, adc[i]);

    show("newest first", head);
    reverse(&head);
    show("oldest first", head);

    while (head != NULL) {
        struct reading *n = head->next;
        free(head);
        head = n;
    }
    return 0;
}
newest first: 540 505 498 530 512
oldest first: 512 530 498 505 540

Why this pattern is popular

Prepending is cheaper than appending on a singly linked list, so firmware often prepends in a time-critical path and reverses once in a relaxed context. One O(n) reversal replaces an O(n) walk on every insert.

Common Mistakes and Troubleshooting

MistakeSymptomFix
Forgetting *head = prevPrinting shows only the old first nodeUpdate head after the loop
Taking struct node *head by valueCaller sees a broken listUse a double pointer
Setting cur->next = prev before saving nextList shrinks to one nodeSave first
Infinite loop when printingFirst node points to itselfStart prev as NULL
Dereferencing cur after the loopNull pointer crashUse prev after the loop

Best Practices and Performance

  • Reversal is O(n) time and O(1) space; avoid reversing inside a tight loop.
  • Prefer the iterative version in embedded code; recursion costs stack per node.
  • Always run linked list code once under AddressSanitizer.
  • In interrupt context, keep list work short; do the reversal in the main loop.

Key Takeaways

  • Four statements in a loop reverse a singly linked list.
  • The head must be updated through a double pointer.
  • Two reversals restore the original list: a handy test.
  • Prepend now, reverse later is a common embedded pattern.

Chapter Quiz: Linked Lists in C

Try each question first, then open the answer.

  1. What does an empty singly linked list look like?
    Answer

    The head pointer is NULL.

  2. Why does push_front() take struct node **?
    Answer

    It must change the caller’s head pointer, and C passes pointers by value.

  3. What is the time cost of adding at the front, and at the back without a tail pointer?
    Answer

    Front is O(1). Back is O(n) because we walk to the last node.

  4. In insert_after(), which assignment must come first: n->next = cur->next or cur->next = n?
    Answer

    n->next = cur->next, otherwise the rest of the list is lost.

  5. When deleting the first node, what is the value of prev?
    Answer

    NULL, so the code updates *head instead of prev->next.

  6. What is wrong with free(p); p = p->next;?
    Answer

    It reads a field of freed memory. Save p->next before freeing.

  7. Why must cur != NULL come before cur->value != value in a loop condition?
    Answer

    && stops at the first false test, so the null check prevents a null dereference.

  8. What does find_position() return for a missing value in our program?
    Answer

    0, because valid positions start at 1.

  9. Which three pointers are used to reverse a list?
    Answer

    prev, cur and next.

  10. Why does prev start as NULL in reversal?
    Answer

    The old first node becomes the last and must point to NULL.

  11. After the reversal loop ends, where does head point?
    Answer

    To prev, the old last node.

  12. What is the space complexity of iterative reversal?
    Answer

    O(1): only three pointer variables.

Practice Challenges

  1. Add menu choice 7 to the complete program that calls reverse_list() and then shows the list.
  2. Write count_nodes() that returns the length of a list.
  3. Write remove_all() that deletes every node equal to a given value.
  4. Write insert_sorted() that keeps a list in ascending order.
  5. Find the middle node of a list using two pointers, one moving twice as fast.

Interview Questions on Linked Lists

1. How do you reverse a singly linked list?

Walk the list with prev, cur and next pointers: save cur->next, point cur->next at prev, move prev and cur forward, and finally set head to prev. It takes O(n) time and O(1) space.

2. Array versus linked list: when would you choose each?

An array gives O(1) random access and is cache friendly. A linked list gives cheap insertion and deletion when you already hold a pointer, and grows without copying. For fixed-size data on small devices, arrays are usually better.

3. How do you detect a loop in a linked list?

Use two pointers, one moving one step and one moving two steps. If they ever meet, there is a loop.

4. How do you find the middle node in one pass?

Move a slow pointer one step and a fast pointer two steps. When the fast one reaches the end, the slow one is at the middle.

5. How do you delete a node when you only have a pointer to it?

For a node that is not last, copy the next node’s data into it and unlink the next node. This does not work for the last node and changes node identity, so it is a trick, not a general method.

6. What are the cases when deleting from a singly linked list?

First node, middle node, last node, and value not found. A trailing prev pointer lets one piece of code cover the first three.

7. Why pass a pointer to the head pointer?

So the function can change which node is first, as in push_front, delete of the first node, and reversal.

8. How do you avoid memory leaks with a linked list?

Free every node you remove, free the whole list before exit, save next before freeing, and test with valgrind or AddressSanitizer.

9. What is the advantage of a doubly linked list?

You can move in both directions and delete a node given only a pointer to it, at the cost of an extra pointer per node.

10. Why is a linked list often avoided in embedded systems?

Each node adds pointer overhead, dynamic allocation can fragment memory or fail, and pointer chasing hurts cache behaviour. Static pools or arrays are common alternatives.

11. How would you merge two sorted linked lists?

Compare the front nodes of both lists, attach the smaller to the result, advance that list, and repeat. Attach the remaining list at the end.

12. What does a dangling pointer mean, and how can it appear in list code?

It is a pointer to memory that was freed. It appears when you use a node pointer after calling free on it.

Conclusion

You have now built a complete linked list toolkit in C: creation, insertion at three places, deletion, display, search, cleanup and reversal. You also practised the habits that matter for real firmware: checking allocations, drawing pointer diagrams and testing edge cases. Keep going with this free C tutorial series, and use these functions as the base for stacks, queues and more advanced structures in your journey through C programming for embedded systems.

Frequently Asked Questions

Can I reverse a linked list without a third pointer?

Not safely for a singly linked list. The third pointer holds the rest of the list while you flip the arrow.

Does reversing change the memory addresses of nodes?

No. Nodes stay where they are; only the next pointers change.

Why prepend and then reverse instead of appending directly?

Prepending is O(1), appending is O(n) without a tail pointer. One reversal at the end is cheaper than many walks.

How do I test my reverse function quickly?

Reverse twice and compare with the original, and test the empty and single-node lists.

Is this course free for students?

Yes. EmbeddedPathashala offers this free C programming course and other free embedded systems, Linux kernel and device driver courses to all learners.

Finish Strong: Free C Programming Course

Practise the challenges, then move on to the next chapter.

PREV_LEC | NEXT_LEC

💬 Need help or career guidance? Ask us!Contact Us →

2 Comments

Leave a Reply

Your email address will not be published. Required fields are marked *

×

🚀 BLE on Linux (BlueZ)

Hands-on course. Only ₹399

Enroll Now →