Skip to content

Instantly share code, notes, and snippets.

@EdgeCaseBerg
Last active August 29, 2015 13:56
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save EdgeCaseBerg/9307188 to your computer and use it in GitHub Desktop.
Save EdgeCaseBerg/9307188 to your computer and use it in GitHub Desktop.
Reverse a forward linked list in Theta(N) time. (Note no checks on malloc because this is a toy program)
#include <stdio.h>
#include <stdlib.h>
struct node
{
struct node * next;
int seq;
};
int main()
{
/* Reverse a forward only list, N time */
//create list:
struct node one; one.seq = 1;
struct node two; two.seq = 2;
struct node three; three.seq = 3;
struct node * head = malloc(sizeof(struct node)); head->next = &one;
struct node * clnup = head; //for your memory leak.
one.next = &two; two.next = &three; three.next = NULL;
for (head = &one; head != NULL; head = head->next)
printf("%d\n", head->seq);
//Traverse
head = &one;
struct node * bckPtr = NULL;
struct node * tmp = NULL;
struct node * orgHead = head;
bckPtr = head;
head = head->next; //prime the pump
for (; head != NULL; ){
tmp = head->next;
head->next = bckPtr;
bckPtr = head;
head = tmp;
}
//flip the original head.
orgHead->next = NULL;
for (head = bckPtr; head != NULL; head = head->next)
printf("%d\n", head->seq);
free(clnup);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment