Oleksandr Gavenko's blog
2018-03-17 12:22 Reverse linked list in-place

It is common interview programming task to reverse singly 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 write:

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.

c, interview

Feeds

all / emacs / java / python

Tags

adb(1), admin(1), android(1), anki(1), blog(1), c(1), css(2), cygwin(2), driver(1), emacs(3), fs(1), git(2), gradle(1), hardware(1), hg(2), html(1), interview(13), java(2), js(3), lang(2), lighttpd(1), mobile(1), naming(1), oracle(1), print(1), problem(5), quiz(6), rst(1), security(1), sql(2), srs(1), style(1), unit(1), utils(1), vcs(3), web(2), win(2), windows(1)

Archive