关于单链表的算法题

//1.顺序表和链表的优缺点。
//顺序表的优点是可以随机访问数据元素；缺点是大小固定，不利于增删结点。
//链表的优点是采用指针方式增减结点，非常方便（只需要改变指针指向，不移动结点）；
//缺点是不能进行随机访问，另外，每个结点上增加指针域，造成额外存储空间增大。
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<string.h>
#include<assert.h>
typedef  int   DataType;
typedef struct  LinkNode
{
	DataType _data;
	struct   LinkNode *_next;
}LinkNode,*pLinkNode;
pLinkNode BuyNode(DataType x);//开辟节点
void  InitNode(pLinkNode& pHead);//初始化
void  DestoryNode(pLinkNode& pHead);//销毁节点
void  PushBack(pLinkNode&  pHead,DataType x);//尾插节点
void  PrintNode(pLinkNode pHead);//打印
void  PrintfFromTail(pLinkNode  pHead);//从尾到头打印链表
void  EraseNoHead(pLinkNode  pos);//删除一个无头单链表的非尾节点
void  InsertNoHead(pLinkNode pos, DataType x);//无头单链表非头节点插入一个节点
void  Joseph(pLinkNode pHead,int  Length);//实现约瑟夫环
void  Reverse(pLinkNode& pHead);//逆置/反转单链表
void  CombineTwoLink(pLinkNode& firstpHead, pLinkNode  secondpHead);
void  SearchMid(pLinkNode  pHead);//查找单链表的中间节点，只能遍历一次
pLinkNode  SearchKNode(pLinkNode pHead,int k);//查找单链表的倒数第k个节点，只遍历一次
pLinkNode BuyNode(DataType x)
{
	pLinkNode tmp;
	tmp = (pLinkNode)malloc(sizeof(LinkNode));
	tmp->_data = x;
	tmp->_next = NULL;
	return  tmp;
}
void  InitNode(pLinkNode& pHead)
{
	pHead=NULL;
}
void  DestoryNode(pLinkNode& pHead)
{
	pLinkNode del=pHead;
	while (pHead!= NULL)//如果phead指向结构体还有数据
	{
		del = pHead;
		pHead = pHead->_next;
		free(del);
	}
}
pLinkNode Find(pLinkNode PLinkhead, DataType x)
{
	pLinkNode  cur = PLinkhead;
	while (cur)
	{
		if (cur->_data == x)
			return cur;
		else
			cur = cur->_next;
	}
	return NULL;
}
void  PushBack(pLinkNode&  pHead, DataType x)
{
	if (pHead == NULL)
	{
		pHead = BuyNode(x);
	}
	else
	{
		pLinkNode newNode = BuyNode(x),cur=pHead;
		while (cur->_next != NULL)
		{
			cur = cur->_next;
		}
		cur->_next = newNode;
	}
}
void  PrintNode(pLinkNode pHead)
{
	assert(pHead);
	while (pHead != NULL)
	{
		printf("%d->", pHead->_data);
		pHead=pHead->_next;
	}
	printf("NULL\n");
}
void  PrintfFromTail(pLinkNode  pHead)
{
	if (pHead == NULL)//递归法
	{
		printf("NULL->");
		return;
	}
	else
		PrintfFromTail(pHead->_next);
	printf("%d->",pHead->_data);
}
void  EraseNoHead(pLinkNode  pos)
{
	assert(pos);
	pLinkNode del = pos->_next;
	pos->_data = pos->_next->_data;//将pos后的值赋值给pos
	pos->_next = pos->_next->_next;
	free(del);
}
void  InsertNoHead(pLinkNode pos, DataType x)
{
	assert(pos);
	pLinkNode  newNode = BuyNode(x);
	newNode->_next = pos->_next;//将新值插入到pos后
	pos->_next= newNode;
	newNode->_data = pos->_data;//拷贝数据
	pos->_data = x;
}
void  Joseph(pLinkNode pHead,int  Length)
{
	assert(pHead);//循环链表
	pLinkNode cur = pHead, del;
	while (1)
	{
		if (cur->_next == cur)
		{
			assert(cur->_data = 4);
			printf("所剩最后：%d\n", cur->_data);
			return;
		}
			
		int times = Length - 1;
		while (times--)
		{
			cur = cur->_next;
		}
		del = cur->_next;
		cur->_data = cur->_next->_data;//拷贝cur的下一个结点的数据，删除它
		cur->_next = del->_next;
		free(del);
	}
}
void  Reverse(pLinkNode& pHead)
{
	assert(pHead);
	pLinkNode newHead = NULL;
	pLinkNode cur = pHead;
	if (cur == NULL || cur->_next == NULL)//如果链表中只有一个元素
		return;
	while (cur)
	{
		pLinkNode tmp = cur;//摘节点
		cur = cur->_next;
		tmp->_next = newHead;//头插
		newHead = tmp;
	}
	pHead = newHead;
}
void  CombineTwoLink(pLinkNode& firstpHead, pLinkNode  secondpHead)
{
	pLinkNode finally =BuyNode(-1),cur=finally,tmp=NULL;
	assert(firstpHead);
	assert(secondpHead);
	while (firstpHead&&secondpHead)
	{
		if (firstpHead->_data < secondpHead->_data)
		{
			tmp = firstpHead;
			firstpHead = firstpHead->_next;
		}
		else
		{
			tmp = secondpHead;
			secondpHead=secondpHead->_next;
		}
		tmp->_next = cur->_next;
		cur->_next = tmp;
		cur = tmp;
	}
	if (firstpHead)
		cur->_next = firstpHead;
	else
		cur->_next = secondpHead;
	firstpHead = finally->_next;
	free(finally);
}
void  SearchMid(pLinkNode  pHead)
{
	pLinkNode fast=pHead, slow=pHead;
	assert(pHead);
	while (fast&&fast->_next&&fast->_next->_next)//考虑只有两个数的情况
	{
		fast = fast->_next->_next;
		slow = slow->_next;
	}
	printf("%d\n",slow->_data);
}
pLinkNode  SearchKNode(pLinkNode pHead,int  k)
{
	pLinkNode fastK=pHead;
	assert(pHead);
	while (fastK&&k--)
	{
		fastK = fastK->_next;
	}
	if (k > 0)
		return NULL;
	while (fastK)
	{
		fastK = fastK->_next;
		pHead = pHead->_next;
	}
	return pHead;
}
//void Test1()
//{
//	pLinkNode Link=NULL;
//	InitNode(Link);
//	PushBack(Link, 1);
//	PushBack(Link, 2);
//	/*PushBack(Link, 3);
//	PushBack(Link, 6);
//	PushBack(Link, 4);
//	PushBack(Link, 5);*/
//	PrintNode(Link);
//	//EraseNoHead(Find(Link, 2));//非尾
//	//PrintNode(Link);
//	//InsertNoHead(Find(Link,3), 7);//非头
//	//PrintNode(Link);
//
//	/*Find(Link, 5)->_next = Find(Link,1);
//	Joseph(Link, 3);*/
//	//PrintfFromTail(Link);
//
//	/*Reverse(Link);*/
//
//	SearchMid(Link);
//	PrintNode(Link);
//  DestoryNode(Link);
//}
void Test2()
{
	pLinkNode target = NULL, source = NULL,kNode=NULL;
	InitNode(target);
	InitNode(source);
	PushBack(target, 1);
	PushBack(target, 3);
	PushBack(target, 4);
	PushBack(target, 6);
	PushBack(target, 9);
	PushBack(source, 3);
	PushBack(source, 5);
	PushBack(source, 7);
	PushBack(source, 10);
	PushBack(source, 12);
	PrintNode(target);
	PrintNode(source);
	
	CombineTwoLink(target, source);
	PrintNode(target);

	DestoryNode(target);
	
	kNode = SearchKNode(target, 3);
	printf("从尾往前第3个数据：\n%d\n", kNode->_data);
}
int main()
{
	//Test1();
	Test2();
	system("pause");
	return 0;
}

本文出自 “小止” 博客，请务必保留此出处http://10541556.blog.51cto.com/10531556/1705531

关于单链表的算法题

原文：http://10541556.blog.51cto.com/10531556/1705531