线性表相关操作

顺序表逆置

void inverse(int a[], int n){
  int t;
  for(int i = 0; i < n; i ++){
    t = a[i];
    a[i] = a[n - i - 1];
    a[n - i - 1] = t;
  }
}

删除带头结点递增有序单链表中开区间(a,b)的所有节点

struct LNode{
  int data;
  struct LNode *next;
}LNode;

void deleteBetweenAandB(LNode *head, int a, int b){
  LNode *p = head;
  LNode *q = head -> next;
  LNode *premin = head, *pmin = head -> next;
  LNode *premax = head, *pmax = head -> next;

  bool flag = false;
  while(q != NULL){
    if(q -> data > a && !flag){
      pmin = q;
      premin = p;
      flag = true;
    }
    else if(q -> data < b){
      pmax = q;
      premax = p;
    }
    p = p -> next;
    q = q -> next;
  }
  premin -> next = pmax -> next;
}

在带头结点的单链表中删除所有值为x的结点

void delete(LNode *head, int x){
  Node *p = head, *q;
  p = p -> next;
  while(p != NULL){
    if(p -> data == x){
      q = p;
      p = q -> next;
      free(q);
    }
    else  p = p -> next;
  }
}

实现单链表的逆置

void invert(LNode *head){
  LNode *p, *q, *r;
  p = head;
  q = p -> next;
  while(q != NULL){
    r = q -> next;
    q -> next = p;
    p = q;
    q = r;
  }
  head -> next = NULL:
  head = p;
  return head;
}

将单链表最小元素放到单链表最前面

struct LNode{
  int data;
  struct LNode *next;
}LNode, *Linklist;

Linklist seek(Linklist &head){
  Linklist p = head, minp;
  minp = p;
  p = head -> next;
  while(p != NULL){
    if(minp -> data > p -> data)
      minp = p;
    p = p -> next;
  }
  return minp;
}

Linklist insert(Linklist &minp, Linklist &head){
  Linklist p = head;
  if(minp = head) return head;
  else{
    if(minp -> next == NULL){
      while(p -> next != minp){
        p = p -> next;
      }
      p -> next = NULL;
      minp -> next = head;
      head = minp;
    }
    else{
      while(p -> next != minp){
        p = p -> next;
      }
      p -> next = minp -> next;
      minp -> next = head;
      head = minp;
    }
    rerturn head;
  }
}

两个递增单链表合并为一个递增单链表

void merge(LNode *A, LNode *B, LNode *&C){
  LNode *p = A -> next;
  LNode *q = B -> next;
  LNode *r;
  C = A;
  C -> next = NULL:
  r = C;
  while(p != NULL && q != NULL){
    if(p -> data <= q -> data){
      r -> next = p;
      p = p -> next;
      r = r -> next;
    }
    else{
      r -> next = q;
      q = q -> next;
      r = r -> next;
    }
  }
  r -> next = NULL;
  if(p != NULL) r -> next = p;
  if(q != NULL) r -> next = q;
}

单链表求两个集合交集

void Interaction(Linklist &A, Linklist &B){
  Linklist pc = A, pa = A -> next, pb = B -> next;
  while(pa && pb){
    if(pa -> data == pb -> data){
      pc -> next = pa;
      pc = pa;
      pa = pa -> next;
      pb = pb -> next;
    }
    else if(pa -> data > pb -> data){
      pb = pb -> next;
    }
    else{
      pa = pa -> next;
    }
  }
  pc -> next = NULL:
  return ;
}

最大值放入单链表最后

void MoveMaxToTail(Linklist &head){
  Linklist p = head, r = head;
  Linklist q = p -> next;
  while(q != NULL){
    if(p -> data < q -> data){
      p = q;
    }
    q = q -> next;
  }
  while(r -> next != p){
    r = r -> next;
  }
  q = head;
  while(q != NULL){
    q = q -> next;
  }
  if(p -> next == NULL){
    return ;
  }
  else{
    r = next = p -> next;
    p -> next = NULL;
    q -> next = p;
  }
}

递归删除不带头节点链表中所以元素为x的节点

void delele_non(Linklist &head, int x){
  Linklist p;
  if(head == NULL) return ;
  if(head -> data == x){
    p = head;
    head = head -> next;
    free(p);
    delele_non(head, x);
  }
  else{
    delele_non(head -> next, x);
  }
}

删除带头节点所有元素为x的节点

void delete(Linklist &head, int x){
  Linklist p = head -> next, pre = head, q;
  while(p != NULL){
    if(p -> data == x){
      q = p;
      p = p -> next;
      pre -> next = p;
      free(q);
    }
    else{
      pre = p;
      p = p -> next;
    }
  }
}

单链表实现直接插入排序

void sort(Linklist &head){
  LNode *p = head -> next, *pre;
  LNode *r = p -> next;
  p -> next = NULL;
  p = r;
  while(p != NULL){
    r = p -> next;
    pre = head;
    while(pre -> next != NULL && pre -> next -> data < p -> data){
      pre = pre -> next;
    }
    p -> next = pre -> next;
    pre -> next = p;
    p = r;
  }
}

判断单链表是否存在环

bool hasCycle(Linklist &head){
  if(head == NULL)  return false;
  Linklist slow = head, fast = head;
  while(fast != NULL && fast -> next != NULL){
    slow = slow -> next;
    fast = fast -> next -> next;
    if(slow == fast)  return true;
  }
  return false;
}