Skip to content

Instantly share code, notes, and snippets.

@dsosby dsosby/PairSwap.c
Last active Dec 16, 2015

Embed
What would you like to do?
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
struct Node *prev;
} Node;
Node* SwapPairs(Node *head)
{
//Except cases
if (!head) return NULL;
if (!head->next) return head;
Node *toReturn = head->next;
while(1) {
Node *left = head->prev;
Node *right = head->next;
if (left) {
//Head's left is currently incorrect...fix
head->prev = head->prev->next;
left = head->prev;
left->next = right ? right : head;
}
if (right) {
head->next = right->next;
head->prev = right;
right->next = head;
right->prev = left;
}
if (!head->next) break;
head = head->next;
};
return toReturn;
}
Node* makeNode(int data, Node *parent)
{
Node *n = malloc(sizeof (*n));
n->data = data;
n->prev = parent;
n->next = NULL;
if (parent) parent->next = n;
return n;
}
void freeNodes(Node *head)
{
Node *nxt = head ? head->next : NULL;
free(head);
if (nxt) freeNodes(nxt);
}
void printNodes(Node *head)
{
if (head) printf("%d ", head->data);
else {
puts("");
return;
}
printNodes(head->next);
}
int main()
{
Node *n = NULL, *test;
test = SwapPairs(n);
assert(test == NULL);
puts("Test 1");
n = makeNode(1, NULL);
n = SwapPairs(n);
assert(n->data == 1);
assert(n->next == NULL);
puts("Test 2");
makeNode(2, n);
n = SwapPairs(n);
assert(n->data == 2);
assert(n->next->data == 1);
puts("Test 3");
makeNode(3, n->next);
n = SwapPairs(n);
assert(n->next->data == 2);
assert(n->next->next->data == 3);
puts("Test 4");
makeNode(4, n->next->next);
n = SwapPairs(n);
assert(n->data == 2);
assert(n->next->data == 1);
assert(n->next->next->data == 4);
assert(n->next->next->next->data == 3);
assert(n->next->next->next->next == NULL);
assert(n->next->next->next->prev == n->next->next);
puts("All passed");
freeNodes(n);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.