链表

节点结构

struct node{
	int data;
	node* next;
}

1.删除指针指向的结点（非头非尾）

狸猫换太子 : 当前结点与其后结点交换

bool deleteNode(node* pCur){
	if(pCur == NULL || pCur -> next == NULL)
		return false;
	node* pNext = pCur -> next;
	pCur -> next = pNext -> next;
	pNext -> data = pCur -> data;
	free(pNext);
	return true;
}

2. 删除单链表节点

node* deleteNode(node* head,int data){
	assert(head != NULL);
	node* p = head;
	node* q = NULL;//p前驱
	while(p != NULL && p->data != data){//寻找删除的结点
		q = p;
		p = p-> next;
	}
	if(p == NULL)//没找到
		return head;
	if(q == NULL){//头指针指向的为data
		q = p;
		p = p -> next;
		free(q);
		return p;
	}
	q -> next = p -> next;//删除的为非头
	free(p);
	return head;
}

3.判断单链表是否有环

快慢两个指针

bool isloop(node* head){
	node* fast = head;
	node* slow = head;
	while(fast -> next != NULL){
	fast = fast -> next -> next;
	slow = slow -> next;
	if(fast == slow)
		return true;
	}
	if(fast -> next == NULL)
		return false;
}

4. 寻找循环链表的入口

node* FindBegining(node* head){
	node* fast = head;
	node* slow = head;
	while(fast -> next != NULL){
		fast = fast -> next -> next;
		slow = slow -> next;
		if(fast == slow)
			break;
	}

	if(fast -> next == NULL)
		return NULL;

	slow = head;
	while(fast != slow){
		fast = fast -> next;
		slow = slow -> next;
	}
	return slow;
}

5.反转单链表

//迭代：头插法
node* ReverseLink(node* head){
	if(head == NULL)
		return NULL;
	if(head -> next == NULL)
		return head;
	node* prev = NULL;
	node* curr = head;
	while(curr){
		node* next = curr -> next;
		curr -> next = prev;
		prev = curr;
		curr = next;
	}
	return prev;
}

//递归法
node* ReverseLinkRecursive(node* head){
	if(head == NULL)
		return NULL;
	node* reverse_head,*temp,*curr;
	if(head -> next == NULL){
		return head;
	}
	else{
		curr = head;
		temp = head -> next;
		reverse_head = ReverseLinkRecursive(temp);
		temp -> next = curr;
		curr -> next = NULL;
	}
	return reverse_head;
}

6.实现环状单向链表，尾指向头，去除连续的重复元素

（头）1->2->2->3->3->1->1（头）去除后：1->2->3

node* unique(node* head){
	if(head == NULL || head == head -> next)
		return head;
	node* p,*q;
	p = head;
	q = head -> next;
	while(q != head){
		while(p -> data == q -> data && q != head){
			p -> next = q -> next;
			free(q);
			q = head -> next;
		}
		if(q == head) break;
		p = q;
		q = p -> next;
	}
	if(p -> data == q -> data){
		p -> next = q -> next;
		free(q);
		return p;
	}
	else 
		return q;
}