Reverse linked list in-place

For example it is mentioned here:

https://www.joelonsoftware.com/2006/10/25/the-guerrilla-guide-to-interviewing-version-30/: The Guerrilla Guide to Interviewing (version 3.0).

During my interview I've spent around 40 min to complete task in online collaborative editor spending most of the time on debugging:

reverse(list);
print(list);

which was off screen where I should have written:

list = reverse(list);
print(list);

Another problems were that I forgot syntax how to declare self reference in C structure declaration, below is wrong syntax:

typedef struct {
    int val;
    list_t *next;
} list_t;

and header name for assert().

Today I implemented task in 15 min:

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

typedef struct list_t {
    int val;
    struct list_t *next;
} list_t;

list_t * list_make(int size) {
    assert(size > 0);
    list_t *head = NULL;
    for (int i = 0; i < size; i++) {
        list_t *tail = head;
        head = malloc(sizeof(list_t));
        head->next = tail;
    }
    return head;
}

void list_incr_fill(list_t *head) {
    for (int i = 1; head != NULL; i++, head = head->next) {
        head->val = i;
    }
}

void list_print(list_t *head) {
    while (head != NULL) {
        printf("%d ", head->val);
        head = head->next;
    }
    puts("");
}

list_t* list_reverse(list_t *head) {
    list_t *rest = head;
    head = NULL;
    while (rest != NULL) {
        list_t *prev = head;
        head = rest;
        rest = rest->next;
        head->next = prev;
    }
    return head;
}

int main() {
    list_t *my = list_make(5);
    list_incr_fill(my);
    list_print(my);
    my = list_reverse(my);
    list_print(my);
    return 0;
}

Run it with:

gcc -o rev.exe rev.c && ./rev.exe

https://en.wikibooks.org/wiki/Data_Structures/Singly_Linked_Lists: Singly Linked Lists.

Feeds

Tags

Archive