linkedlist

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

struct Node
{
  int data;
  struct Node *next;
};
struct Node *fist = NULL;

void create(int A[], int n)
{
  struct Node *t, *last;
  
  // first create the first node for first;
  first = (struct Node *)malloc(sizeof(struct Node));
  first->data = A[0];
  first->next = NULL;
  last = first;
  
  for (int i = 1; i < n; i++) {
    t = (struct Node *) malloc(sizeof(struct Node));
    t->data = A[i];
    t->next = NULL;
    last->next = t;
    last = t;
  }
}
void display(struct Node *P)
{
  while (P) {
    printf("%d ", P->data);
    P= P->next;
 }
}
void Rdisplay(struct Node *P)
{
  while (P != NULL) 
  {
    printf("%d ", P->data);
    Rdisplay(P->next);
  }
}

int count(struct Node *P)
{
  int c = 0;
  while (P) 
  {
    c++;
    P = P->next;
  }
  return c;
}
int Rcount(struct Node *P)
{
  if (!P) return 0;
  return 1 + Rcount(P->next);
}

int sum(struct Node *P)
{
  int sum = 0;
  while (P)
  {
    sum += P->data;
    P = P->next;
  }
  return sum;
}

int Rsum(struct Node *P)
{
  if (P == NULL) return 0;
  return P->data + Rsum(P->next);
}

int max(struct Node *p)
{
  int max = MIN_INT;
  while(p)
  {
    if (p->data > max ) max = p->data;
    p = p->next;
  }
  return max;
}

int Rmax(struct Node *p)
{
  if (!p) return MIN_INT;
  int max = p->data;
  int new = max(p->next);
  if ( max < new ) max = new;
  return max;
}

struct Node * search (struct Node *p, int key)
{
  while(p) 
  {
    if (p->data == key ) return p;
    p = p->next;
  }
  return NULL;
}

struct Node * Lsearch(struct Node *p, int key)
{
  if ( p == NULL ) return NULL;
  struct Node *q = p;
  while ( p ) {
    if ( p->data == key) {
      q->next = p->next;
      p->next = first;
      first = p;
      return p;
    } else {
      q = p;
      p  = p->next;
    }
  }
  return NULL;
}
struct Node *Rsearch(struct Node *p, int key)
{
  if (p==NULL) return NULL;
  if(p->data = key) return p;
  return Rsearch(p->next);
}

void Insert(struct Node *p, int pos, int x)
{
  
  struct Node *t = (struct Node *) malloc(sizeof(struct Node));
  struct Node *q = NULL;
  t->data = x;
  t->next = NULL;
  if (pos == 0 ) {
    // insert before the first
    if ( first == NULL) {
      first = t;
    } else {
      t->next = first->next;
      first = t;
    }
  } else {
    for(int i = 0; i < pos-1 && p ; i++)
    {
      q = p;
      p = p->next;
    }
    if (p == NULL) p = q;
    if (p) {
      t->next = p->next;
      p->next = t;
    }  
  }
}
void InsertLast(int x)
{
  struct Node * last, *t;
  t = (struct Node *) molloc(sizeof(struct Node));
  t->data = x;
  t->next = NULL;
  if ( first == NULL){
    first = last = t;
  } else {
    last->next = t;
    last = t;
  }
}
void InsertSorted(struct Node *p, int x)
{
  struct Node *t = (struct Node*) malloc(struct Node));
  t->data = x;
  t->next = NULL;
  struct Node *q = NULL;
  if ( first == NULL) {
    first = t;
  } else {
    while( p && p->data < x ) 
   {
      q = p;
      p = p->next;
    }
    if ( p == first ) {
      t->next = first;
      first = t;
    } else {
      t->next = q->next;
      q->next = t;
    }
   }
  }
}
void Delete(int x)
{
  if(first == NULL) return;
  struct Node *p, *q, *t;
  p = q = first;
  while ( p && p->data != x) {
    q = p;
    p = p->next;
  }
  if ( p == first ) {
    t = first;
    first = first->next;
    delete t;
  } else if ( p != NULL) {
    q->next = p->next;
    delete p;
  }
}

void Delete(index pos)
{
  if ( first == NULL) return;
  if ( pos <= 0 || pos >= count(first)) return;
  struct Node *q, *p, *t;
  p = q = first;
  if ( pos == 0) {
    t = first;
    first = first->next;
    delete t;
  } else {
    for ( int i = 0; i < pos-1;i++) {
      q = p;
      p = p->next;
    }
    q->next = p->next;
    delete p;
  }
}

void RemoveDuplicate(struct Node *p)
{
  struct Node *q;
  if (!p) return;
  q = p->next;
  while(q) {
    if (p->data == q->data) {
      p->next = q->next;
      delete q;
      q = p->next;
    } else {
      p = p->next;
      q = q->next;
    }
  }
}

void Reverse(struct Node *p)
{
  struct Node *q, *r;
  q = r = NULL;
  while(p) {
    r = q;
    q = p;
    p = p->next;
    q->next = r;
  }
  first = q;
}

void RReverse(struct Node *q, struct Node *p)
{
  while (p) {
    RReverse(p,p->next);
    p->next = q;
 }
 first = q;
}

void ReverseByElements(struct Node *p)
{
  int n = count(p);
  int *A;
  A = (int *)malloc(sizeof(int) * n);
  struct Node *q = p;
  int i = 0;
  while (q) 
  {
    A[i++] = q->data;
    q = q->next;
  }
  q = p;
  i--;
  while (q)
  {
    q->data = A[i--];
    q = q->next;
  }
} // this is not the good one
  // 1. if the data is very large, this method needs a lot of memory
  // 2. in the real project, these data could be used somewhere else, so if the data is changed, 
  //that will produce the reverse effect
struct Node * Concatenate(struct Node *p1, struct Node *p2)
{
  struct Node *p = p1;
  while(p1 && p1->next) 
    p1 = p1->next;
  p1->next = p2;
  return p;
}

struct Node * MergeSorted(struct Node *p1, struct Node *p2)
{
  struct Node *q, *last;
  
  if (p1 == NULL) return p2;
  if (p2 == NULL_ return p1;
  if ( p1->data < p2->data) {
    q = last = p1;
    p1 = p1->next;
    last->next = NULL;
  } else {
    q = last = p2;
    p2 = p2->next;
    last->next = NULL;
  }
  while ( p1 && p2) {
    if (p1->data < p2->data) {
      last->next = p1;
      last = p1;
      p1 = p1->next;
      last->next = NULL;
    } else {
      last->next = p2;
      last = p2;
      p2 = p2->next;
      last->next = NULL;
    }
  }
  if ( p1 ) last->next = p1;
  if ( p2 ) last->next = p2;
  return q;
}

int main() 
{
  int A[] = {1, 2, 3, 4, 5};
  create(A, 5);
  display(first);
  return 0;
}