Skip to content

Instantly share code, notes, and snippets.

@gboncoffee
Created September 22, 2023 00:37
Show Gist options
  • Save gboncoffee/9782114a5682c703d4ef1a417e451162 to your computer and use it in GitHub Desktop.
Save gboncoffee/9782114a5682c703d4ef1a417e451162 to your computer and use it in GitHub Desktop.
Inverting a Linked List in linear time
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
typedef struct LL {
int d;
struct LL *r;
} LL;
LL *cons(int d, LL *r)
{
LL *new = (LL*) malloc(sizeof(LL));
assert(new != NULL || "no memory :(");
new->d = d;
new->r = r;
return new;
}
void destroy_l(LL *l)
{
if (l != NULL) {
destroy_l(l->r);
free(l);
}
}
void print_l(LL *l)
{
if (l == NULL) {
printf("[]\n");
return;
}
printf("%d : ", l->d);
print_l(l->r);
}
/* this function shouldn't be used directly, in Haskell I would name it
* revert' */
LL *revert_in(LL *l)
{
LL *p;
LL *r;
if (l->r == NULL)
return l;
p = revert_in(l->r);
r = l->r;
(l->r)->r = l;
l->r = r;
return p;
}
LL *revert(LL *l)
{
LL *n;
if (l == NULL)
return NULL;
n = revert_in(l);
l->r = NULL;
return n;
}
int main(void)
{
/* test with big list */
LL *l = cons(1, cons(2, cons(3, cons(4, cons(5, cons(6, cons(7, NULL)))))));
print_l(l);
l = revert(l);
print_l(l);
destroy_l(l);
/* test with empty list */
l = NULL;
print_l(l);
l = revert(l);
print_l(l);
/* test with single item list */
l = cons(1, NULL);
print_l(l);
l = revert(l);
print_l(l);
destroy_l(l);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment