0.数据结构

typedef struct LNode{//链表结点
	int data;
	struct LNode* next;
}LNode,*Linklist;

1.头插

Linklist headInsert(Linklist &L){
	L = new LNode();
	LNode *s;//插入结点
	int x;
	s = (Linklist)malloc(sizrof(LNode));
	s->data = x;
	s->next = L->next;
	L->next = s;
	return L;
}

2.尾插

Linklist tailInsert(Linklist &L){
	L = new LNode();
	LNode *r = L;//尾指针
	int x;
	scanf("%d",x);
	while(x != NULL){
		s = (Linklist)malloc(sizrof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		scnaf("%d",x);
	}
	return L;
}

3.原地逆置（重要）

• 头插是生来逆序的，依次头插即可

LinkList Reverse(Linklist &L){
	LNode *p = L->next;
	LNode *s = p;//头插防断链
	L->next = NULL;//L置空
	while(p != NULL){
		s = p->next;
		p->next = L->next;
		L->next = p;
		p = s
	}
	return L;
}

4.无序单链表，删除介于s和t之间的所有元素

• 双指针构成前驱后继方便删除

LinkList delete_st(Linklist &L,int s,int t){
	LNode *p = L->next;
	LNode *pre= L;//指向p的前驱
	while(p != NULL){
		if(p->data>=s && p->data<=t){//需要删除
			pre->next = p->next;
			free(p);
			p = pre->next;
		}
		else{
			pre = p;
			p = p->next;
		}
	}//while end
	return L;
}

5.找出两个单链表的公共结点

• 长的先移动k位，之后同步移动，无需多言

int length(Linklist L){
	int l = 0;
	LNode *p = L->next;
	while(p != NULL){
		p = p->next;
		l++;
	}
	return L;
}
LNode* same_Node(Linklist &L1,Linklist &L2){
	int l1 = length(L1);
	int l2 = length(l2);
	int k = 0;//长度之差
	LNode *p = L1->next;
	LNode *q = L2->next;
	if(l1 > l2){
		k = l1 - l2;
		while(--k)
			p = p->next;
	}
	else{
		k = l2 - l1;
		while(--k)
			q = q->next;	
	}
	while(p != q){
		p = p->next;
		q = q->next;
	}
	return p;
}

6.将链表A分成A和B，A中保存原链表序号为奇数的结点，B中保存原链表中序号为偶数的结点，且保持相对顺序不变

void divide(Linklist &A){
	Linklist B = (LNode*)malloc(sizeof(LNode));
	B->next = NULL;
	LNode *p = A->next;
	LNode *q = p->next;
	LNode *r = B;
	while(q != NULL){
		p = q->next;
		q->next = r->next;
		r->next = q;
		r = q;
		q = p->next;
	}
	return ;
}

//法2：p保存原表第一个节点后，原表置空，之后奇数插A，偶数插B;

void divide(Linklist &A){
	LinkList B = (LNode*)malloc(sizeof(LNode));
	LNode *p = A->next;
	A->next = NULL;
	LNode *ra = A;
	LNode *rb = B;
	int i = 1;//标记当前序号是奇数还是偶数
	while(p != NULL){
		if(i % 2 != 0){
			ra->next = p;
			ra = p;
			p = p->next;
			i++;
		}
		else{
			rb->next = p;
			rb = p;
			p = p->next;
			i++;
		}
	}
	ra->next = NULL;
	rb->next = NULL;
	return ;
}

7.将线性表C={a1,b1,a2,b2…an,bn}就地拆成A = {a1,a2…an}，B = {bn…b2,b1}

void divide(Linklist &C){
	Linklist A = (Linklist)malloc(sizeof(LNode));
	Linklist B = (Linklist)malloc(sizeof(LNode));
	LNode*p = C->next;
	LNode*r = A;//A的尾指针
	LNode*h = B;//B的头指针
	LNode *s;//头插防止断链
	int i = 0;//标记当前结点是A的还是B的
	while(p!=NULL){
		if(i % 2 != 0){//当前结点尾插到A
			r->next = p;
			r = p;
			p = p->next;
		}
		else{
			s = p->next;
			p->next = h->next;
			h->next = p;
			p = s;
		}
	}
	r->next = NULL;
}

8.删除单链表中数值相同的元素