8.14 day11 链表基础 头插

Linklist headinsert(Linklist &L){
	L = new LNode();
	LNode * s;//要插入的结点
	int x；//要插入的值
	std::cin >> x;
	while (x != -1){
		s = new LNode();
		s->data = x;
		s->next = L->next;
		L->next = s;
		std::cin >> x;
	}
	return L;
}

8.15 day12 链表基础 尾插

Linklist tailinsert(Linklist &L){
	L = (Linklist)malloc (sizeof(LNode));
	LNode *s;
	int x;
	LNode * r = L;//尾结点
	std::cin >> x;
	while(x != -1){
		s = (Linklist)malloc(sizeof(LNode));
		s->data = x;
		r->next = s;
		r = s;
		std::cin >> x;
	}
	r->next = NULL;
	return L;
}

8.17 day13 链表基础 原地逆置

思路：头插法自带逆序buff，将头结点之后的元素依次头插在头结点之后即可

void reverse(Linklist &L){
	LNode *p = L->next;
	LNode *s;//头插防断链
	L->next = NULL;// L:o , p:o->o->o->o->o//象形文字,将以p为第一个结点的链表头插在L后面
	while(p != NULL){
		s = p->next;
		p->next = L->next;
		L->next = p;
		p = s;
	}
	return ;	
}

8.18 day14 给定单链表，内部元素无序，删除表中所有介于给定值的元素

bool del(Linklist &L,int s,int t){
	if(L->next == NULL)
		return false;
	if(s > t)
		return false;
	LNode *p = L->next;
	LNode *r = L;
	while(p != NULL){
		if(p->data>=s && p->data<=t){
			r->next = p->next;//注意以下三行代码
			free(p);
			p = r->next;
		}
		p = p->next;
		r = r->next;
	}
	return true;
}

8.19 day15 找出两个单链表的公共结点

思路：让长度短的链表先移动k个位置，k为长度差，再两个结点同时移动；

int length(Linklist &L){
	int count = 0;
	LNode* p = L->next;
	while(p != NULL){
		p = p->next;
		count ++;
	}
	return count;
}

Linklist same_Node(Linklist &l1,LinkList &l2){
	LNode *p = l1->next;
	LNode *q = l2->next;
	int k = length(l1) - length(l2);
	if(k >= 0){//l1长,则l2先移k个位置
		while(--k != 0)
			q = q->next;
	}
	else{
		while(++k != 0)
			p = p->next;
	}
	while(p!=NULL && q!=NULL){
		if(p == q)
			return p;
		p = p->next;
		q = q->next;
	}
	return NULL;
}

8.20 day16 将一个单链表A分成两个单链表A和B，使得A表中含有原表中序号为奇数的元素，B表中含有原表序号为偶数的元素，且保持相对顺序不变（尾插）

void divide(Linklist &A){
	LNode *p = A->next;//p指向原表第一个结点
	LNode *q = p->next;//q指向原表第二个结点
	Linklist B = (LNode*)malloc(sizeof(LNode));//头结点
	B->next = NULL;
	LNode *r = B;//链表B的尾指针
	while(q != NULL){
		p = q->next;
		q->next = r->next;
		r->next = q;
		r = q;
		q = p->next;
	}//尾插
	return ;
}

大师兄方法：p保存原表第一个结点后，原表置空，奇数结点尾插到A，偶数结点尾插到B。

void divide(Linklist &A){
	Linklist B = (Linklist)malloc(sizeof(LNode*));
	LNode *p = A->next;//p指向原表第一个结点
	LNode *ra = A;
	LNode *rb = B;
	A->next = NULL;//原表置空（p已经保存了原表的链接）
	int i = 0;//记录原表中结点的序号
	while (p != NULL){
		i++;
		if(i % 2 == 0){//偶结点尾插到B
			rb->next = p;
			rb = p;
		}
		else {
			ra->next = p;
			ra = p;
		}
		p = p->next;//在这里p就重置到下一个结点了
	}//while end
	ra->next = NULL;
	rb->next = NULL;
}

8.23 day17 线性表C={a1,b1,a2,b2…..an,bn}，就地拆成两个线性表A={a1,a2…an},B={bn….b2,b1}