单链表尾插、求单链表中间节点、删除单链表指定元素、单链表逆置、求单链表倒数第K个节点、检测单链表是否为回文结构、求两个单链表交点、判断一个单链表是否带环、单链表销毁

//单链表节点定义、尾插及输出
#include<iostream>
#include<malloc.h>
#include<assert.h>
using namespace std;

typedef struct listNode
{
	struct listNode* next;
	int data;
}node;

//分为两种情况，链表为空和链表不为空
void lastInsert(node** list,int da)
{
	node* n = (node*)malloc(sizeof(node));
	n->data = da;
	n->next = NULL;
	if (n == NULL)
	{
		return;
	}

	if (*list == NULL)
	{
		*list = n;
	}
	else
	{
		node* cur = *list;
		while (cur->next)
		{
			cur = cur->next;
		}
		cur->next = n;

	}

}
void printList(node* list)
{
	node* p = list;
	while (p)
	{
		cout << p->data << " ";
		p = p->next;
	}
	cout << endl;

}

//链表的中间节点  1 2 3 4 5 返回3       1 2 3 4 5 6 返回4
node* middleNode(node* list)
{
	if (list == NULL)
	{
		return NULL;
	}
	int count = 0;
	node* p = list;
	while (p)
	{
		++count;
		p = p->next;
	}
	p = list;
	for (int i = 0; i < count / 2; i++)
	{
		p = p->next;
	}
	return p;
}

//找中间节点方法2  快慢指针法  fast每次走两步  slow每次走一步   fast走到空（偶数）或者走到最后一个元素（奇数），此时slow为中间元素
node* middleNode2(node* list)
{
	if (list == NULL)
	{
		return NULL;
	}
	int count = 0;
	node* fast = list;
	node* slow = list;
	while (fast && fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;
	}
	return slow;
}

//删除链表中指定元素  6  1  3  4  6      ->   1 3  4(例如删除6，剩下1 3 4）
node*  deleteElem(node** plist, int data)
{
	node* cur = *plist;
	node* prev = NULL;
	while (cur)
	{
		if (cur->data == data)
		{ 
			//如果要删的是第一个节点
			if (cur == *plist)
			{
				*plist = cur->next;
				free(cur);
				cur = *plist;
			}
			else
			{
				prev->next = cur->next;
				free(cur);
				cur = prev->next;
			}

		}
		else
		{
			prev = cur;
			cur = cur->next;
		}
	}
	return *plist;
}

void destory(node** plist)
{
	assert(plist);
	node* cur = *plist;
	while (cur)
	{
		*plist = cur->next;
		free(cur);
		cur = *plist;
	}
}

//单链表逆置  1 2 3 4 5   -> 5 4 3 2 1
node* reverseList(node** plist)
{
	node* cur = *plist;
	node* prev = NULL;
	node* next = NULL;
	while (cur)
	{
		next = cur->next;
		cur->next = prev;
		prev = cur;
		cur = next;
	}
	return prev;
}


//求单链表倒数第K个节点   例如 1 2 3 4 5 求倒数第二个   返回2
//思路一：求出链表个数，然后让指针往后走N-K步，比如5-2=3步
//思路二：用fast和slow两个指针，让fast先往后走K个，然后让两个指针同时往后走，当fast为空时，slow此时指向的是倒数第K个节点
//思路二实现
int lastKnode(node** list,int k)
{
	node* fast = *list;
	node* slow = *list;
	while (k--)
	{
		if (fast == NULL)
		{
			return NULL;
		}
		fast = fast->next;
	}
	while (fast)
	{
		fast = fast->next;
		slow = slow->next;
	}
	return slow->data;
 }

//扩展：删除单链表倒数第K个节点
//思路：先找到倒数第K个节点，然后删除




//检测链表是否为回文结构
//思路一：将链表元素放入数组，借助数组来判断链表是否为回文结构
//思路二：找到中间节点（偶数个的话找到后面那个）,然后断开链表，将其中一个链表逆置。判断两个链表对应位置元素是否相等
//判断回文结构思路一
bool ishuiWen(node** list)
{
	if (*list == NULL)
	{
		return true;
	}
	int a[100];
	node* cur = *list;
	int k = 0;
	while (cur)
	{
		a[k++] = cur->data;
		cur = cur->next;
	}
	int low = 0, high = k - 1;
	while (low < high)
	{
		if (a[low] != a[high])
		{
			return false;
		}
		low++;
		high--;
	}
	return true;

}
//判断回文结构思路二
bool ishuiWen2(node** list)
{
	//先找到中间节点
	node* fast = *list;
	node* slow = *list;
	node* middle = NULL;
	node* middle_prev = NULL;
	node* cur = *list;
	bool flag = true;
	while (fast && fast->next)
	{
		fast = fast->next->next;
		middle_prev = slow;
		slow = slow->next;
	}
	middle = slow;

	//断开链表
	middle_prev->next = NULL;
	
	//再逆置后半部分
	 middle=reverseList(&middle);

	//比较两者是否相等
	while (cur && middle)
	{
		if (cur->data != middle->data)
		{
			flag = false;
			break;
		}
		cur = cur->next;
		middle = middle->next;
	}

	//恢复链表
	 middle = reverseList(&middle);
	middle_prev->next = middle;
	return flag;
}

//判断两个链表是否相交，并求交点   该方法在main中没有测试
node* getJiaoDian(node** list1, node** list2)
{
	if (*list1 == NULL || *list2 == NULL)
	{
		return NULL;
	}
	//判断两个链表是否相交（看最后一个节点地址是否相同，并同时求节点个数）
	node* cur1 = *list1;
	node* cur2 = *list2;
	int count1 = 1;
	int count2 = 1;


	while (cur1->next)
	{
		count1++;
		cur1 = cur1->next;
	}
	while (cur2->next)	
	{
		count2++;
		cur2 = cur2->next;
	}
	if (cur1 != cur2)
	{
		return NULL;//这步如果能往下走，说明两个链表是相交的
	}
	cur1 = *list1;
	cur2 = *list2;

	//求交点   让长的链表先走差值步，两个指针再同时往后走，则一定会遇到交点
	int k = count1 - count2;
	if (k>0)
	{
		while (k--)
		{
			cur1 = cur1->next;
		}	
	}
	else
	{
		while (k++)
		{
			cur2 = cur2->next;
		}
		
	}
	while (cur1!=cur2)
		{
			cur1 = cur1->next;
			cur2 = cur2->next;
		}
	return cur1;//或者cur2
}


//该方法也没有在main中测试
//判断一个链表是否带环  如果有环，让fast每次走两步，slow每次走一步，fast一定会追上slow
bool isCircle(node** list)
{
	node* fast = *list;
	node* slow = *list;
	while (fast && fast->next)
	{
		fast = fast->next->next;
		slow = slow->next;
		if (fast == slow)
			return true;
	}
	return false;
}

int main()
{
	node* list=NULL;  //注意在定义一个node*节点后，要将其赋值为NULL，否则程序会崩溃
	//lastInsert(&list, 3);
	lastInsert(&list,1);
	lastInsert(&list, 2);
	lastInsert(&list, 3);
	lastInsert(&list, 2);
	lastInsert(&list, 5);
	printList(list);

	//输出单链表中间节点
	//node* n = middleNode2(list);
	//cout << n->data << endl;

	//删除单链表中指定元素
	//node* list2=deleteElem(&list, 3);
	//printList(list2);


	//逆置单链表
	//node* list3 = reverseList(&list);
	//printList(list3);

	//求倒数第K个节点
	int res = lastKnode(&list, 2);
	cout << "倒数第2个节点为：" << res << endl;


	//判断链表是否为回文结构
	bool b = ishuiWen2(&list);
	if (b)
	{
		cout << "链表是回文结构" << endl;
	}
	else
	{
		cout << "链表不是回文结构" << endl;
	}



	//销毁单链表   注意此处不能同时销毁
	destory(&list);
	//destory(&list2);

	return 0;

}