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 mentioned here:

https://www.joelonsoftware.com/2006/10/25/the-guerrilla-guide-to-interviewing-version-30/

The Guerrilla Guide to Interviewing (version 3.0).

At interview with online editor I spent 40 min to complete task with many time spent debugging:

reverse(list);
print(list);

where I should write:

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

Today I implemented it 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 *tail = head;
    head = NULL;
    while (tail != NULL) {
        list_t *old_head = head;
        head = tail;
        tail = tail->next;
        head->next = old_head;
    }
    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;
}

To run I use:

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

The problem was that I forgot syntax how to declare self reference in structure declaration, below is wrong syntax:

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

and forgot header name for assert().

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(12), 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