顺序表逆置
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;
}