Swap every 2 nodes of a Linked List

// INPUT : a->b->c->d->e->f
// OUTPUT : b->a->d->c->f->e

void swapAdjacent(Node **headRef){
    Node *curr = *headRef;
    Node *prev = NULL;
    Node *currNext;
    if(curr == NULL){
        return;
    }
    while(curr->next != NULL){
        currNext = curr->next;
        curr->next = currNext->next;
        currNext->next = curr;
        if(*headRef == curr){
            *headRef = currNext;
        } else {
            prev->next = currNext;
        }
        if(curr->next != NULL){
            prev = curr;
            curr = curr->next;
        }
    }
}

Reverse a Linked List

#include<stdio.h>

typedef struct node{
int d;
struct node *next;
}Node;

Node* newNode(int data){
Node *n = (Node *)malloc(sizeof(Node));
n->d = data;
n->next = NULL;
return n;
}

void insert(struct node **headRef, int data){
Node *head = *headRef;
Node *temp;
if(head == NULL){
head = newNode(data);
} else {
temp = newNode(data);
temp->next = head;
head = temp;
}
*headRef = head;
}

void displayList(Node *head){
while(head != NULL){
printf("%d ",head->d);
head = head->next;
}
}

void reverseList(Node **headRef){
Node *head = *headRef;
Node *prev = NULL;
Node *temp;
if(head == NULL){
return;
}
while(head->next != NULL){
temp = head->next;
head->next = prev;
prev = head;
head = temp;
}
head->next = prev;
*headRef = head;
}

int main(){
Node *head = NULL;
int i;
for(i=10;i>0;i--){
insert(&head,i);
}
displayList(head);
reverseList(&head);
printf("\nafter reversing\n");
displayList(head);
return 0;
}

Convert Singly Linked List to height balanced BST

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
 int data;
 struct node *next;
 struct node *left;
}LNode;

LNode* newNode(int data){
 LNode *n = (LNode*)malloc(sizeof(LNode));
 n->data = data;
 n->next = NULL;
 n->left = NULL;
 return n;
}

void buildList(LNode **headRef){
 int i;
 for(i=7;i>0;i--){
  LNode *n = newNode(i);
  n->next = *headRef;
  *headRef = n;
 }
}

void freeMem(LNode *head){
    LNode *temp;
    while(head != NULL){
        temp = head;
        head = head->next;
        free(temp);
    }
}

void display(LNode *head){
 while(head->next != NULL){
  printf("%d->",head->data);
  head = head->next;
 }
 printf("%d\n",head->data);
}


LNode* buildBST(LNode* head){
        if(head == NULL || head->next == NULL) return head;
        LNode *root = NULL;
        LNode *slow = head;
        LNode *fast = head;
        LNode *prev = NULL;
        while(fast != NULL && fast->next != NULL){
                prev = slow;
                slow = slow->next;
                fast = fast->next->next;
        }

        root = slow;
        prev->next = NULL;
        root->left = buildBST(head);
        root->next = buildBST(slow->next);
        return root;
}

void preorder(LNode* root){
 if(root != NULL){
  printf("%d ",root->data);
  preorder(root->left);
  preorder(root->next);
 }
}

void inorder(LNode* root){
 if(root != NULL){
  inorder(root->left);
  printf("%d ",root->data);
  inorder(root->next);
 }
}

void postorder(LNode* root){
 if(root != NULL){
  postorder(root->left);
  postorder(root->next);
  printf("%d ",root->data);
 }
}

int main(){
 LNode *head = NULL;
 LNode *root = NULL;
 buildList(&head);
 display(head);
 root = buildBST(head);
 preorder(root);
 printf("\n");
 inorder(root);
 printf("\n");
 postorder(root);
// freeMem(head);
 return 0;
}

Delete all matching elements in the Linked List

// INPUT : 1->2->3->4->5
// OUTPUT : 2->3->4->5 for deleteNode(head,1);

#include<stdio.h>
#include<stdlib.h>

typedef struct node{
 int data;
 struct node *next;
}Node;

Node* newNode(int data){
 Node *n = (Node*)malloc(sizeof(Node));
 n->data = data;
 n->next = NULL;
 return n;
}

void buildList(Node **headRef){
 int i;
 for(i=10;i>0;i--){
  Node *n = newNode(i);
  n->next = *headRef;
  *headRef = n;
 }
}

void freeMem(Node *head){
    Node *temp;
    while(head != NULL){
        temp = head;
        head = head->next;
        free(temp);
    }
}

void display(Node *head){
 while(head->next != NULL){
  printf("%d->",head->data);
  head = head->next;
 }
 printf("%d\n",head->data);
}

Node* deleteNode(Node* head,int data){
Node* temp;
Node* n;
temp = head;
while(temp != NULL){
if(temp->data == data){
head = temp->next;
temp->next = NULL;
free(temp);
temp = head;
continue;
}
n = temp->next;
if(n != NULL && n->data == data){
temp->next = n->next;
n->next = NULL;
free(n);
continue;
}
if(n == NULL){
break;
} else {
temp = temp->next;
}
}
return head;
}

int main(){
 Node *head = NULL;
 buildList(&head);
 display(head);
 head = deleteNode(head,1);
 display(head);
 freeMem(head);
 return 0;
}

Pairwise swapping of nodes in a Linked List

//pairwise swapping of linkedlist nodes

//INPUT : 1->2->3->4->5->6->7->8->9->10

// OUTPUT : 2->1->4->3->6->5->8->7->10->9

#include<stdio.h>

#include<stdlib.h>

typedef struct node{

int data;

struct node *next;

}Node;

void pairwiseSwap(Node **headRef){

Node *current = *headRef;

Node *temp;

Node *prev = NULL;

while(current != NULL && current->next != NULL){

temp = current->next;

current->next = temp->next;

temp->next = current;

if(prev != NULL){

prev->next = temp;

}

if(current == *headRef){

*headRef = temp;

}

prev = current;

current = current->next;

}

}

Node* newNode(int data){

Node *n = (Node*)malloc(sizeof(Node));

n->data = data;

n->next = NULL;

return n;

}

void buildList(Node **headRef){

int i;

for(i=10;i>0;i--){

Node *n = newNode(i);

n->next = *headRef;

*headRef = n;

}

}

void freeMem(Node *head){

    Node *temp;

    while(head != NULL){

        temp = head;

        head = head->next;

        free(temp);

    }

}

void display(Node *head){

while(head->next != NULL){

printf("%d->",head->data);

head = head->next;

}

printf("%d\n",head->data);

}

void main(){

Node *head = NULL;

buildList(&head);

display(head);

pairwiseSwap(&head);

display(head);

freeMem(head);

}