Skip to content

Instantly share code, notes, and snippets.

@yodalee
Created September 3, 2016 17:16
Show Gist options
  • Save yodalee/72489a3d4c385f04f7881ee899ab1859 to your computer and use it in GitHub Desktop.
Save yodalee/72489a3d4c385f04f7881ee899ab1859 to your computer and use it in GitHub Desktop.
swap list
#include <stdio.h>
#include <stddef.h>
typedef struct _List {
struct _List *next;
int val;
} List;
enum {
SWAPSUCCESS,
EMPTYLIST,
INVALIDSWAP,
};
int swap_list(List **head, List *a, List *b) {
// a, b identical
if (a == b) { return SWAPSUCCESS; }
// a, b not exist
if (a == NULL || b == NULL) { return INVALIDSWAP; }
// empty list
if (*head == NULL) { return EMPTYLIST; }
List dummy;
dummy.next = *head;
List *p1 = &dummy;
while(p1->next) {
if (p1->next == a || p1->next == b) {
// find swap point
List *target = (p1->next == a)? b : a;
List *p2 = p1->next;
while(p2->next) {
if (p2->next == target) {
// find swap point, do swap
p2->next = p1->next;
p1->next = target;
target = target->next;
p1->next->next = p2->next->next;
p2->next->next = target;
*head = dummy.next;
return SWAPSUCCESS;
}
p2 = p2->next;
}
return INVALIDSWAP;
}
p1 = p1->next;
}
return INVALIDSWAP;
}
void
printList(List *p)
{
while(p) {
printf("%d->", p->val);
p = p->next;
}
printf("NULL\n");
}
int main(int argc, char *argv[])
{
List l[10];
// build list
for (int i = 0; i < 10; ++i) {
l[i].val = i;
l[i].next = &(l[i+1]);
}
l[9].next = NULL;
//do swap
List *p = l;
printList(p);
swap_list(&p, &l[0], &l[9]);
printList(p);
swap_list(&p, &l[3], &l[5]);
printList(p);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment