链表基本操作

学习链表有段时间了，今天给大家整理了有关链表的基本操作，例如链表的创建、增、删、查等基本操作

结构体定义

typedef int DataType;

typedef struct ListNode
{
	DataType data;
	struct ListNode *next;
} ListNode;

头文件的定义

其中包含了面试题的头文件

void ListInit(ListNode **Node);

void ListDestroy(ListNode **Node);

void ListPushFront(ListNode **Node,DataType data);

void ListPushBack(ListNode **Node,DataType data);

void ListPopFront(ListNode **Node);

void LIstPopBack(ListNode **Node);

ListNode* ListFind(ListNode *Node , DataType data);

void ListInsert(ListNode **Node,ListNode *pos,DataType data);

void ListDelete(ListNode **Node,ListNode *pos);

// 删除一个无头单链表的非尾结点（不能遍历链表）
void ListDelNotFirst(ListNode **Node ,ListNode *pos);

//递归写法
void ListReversePrint(ListNode *Node);

void ListReveresePrint2(ListNode *Node);

void ListPrint(ListNode *Node);

void ListIntersection(ListNode *list1,ListNode *list2);
void TestListInterstion();

ListNode* ListJosephCircle(ListNode *list,DataType k);
void TestListJosephCircle();

ListNode *ListMerge(ListNode *list1,ListNode *list2);
void TestMerge();

void ListFindMidNode(ListNode *list);
void TestFindMid();

void ListFindTailK(ListNode *list,DataType k);
void TestFindTailK();

void ListDelTailK(ListNode *list, DataType k);
void TestDelTailK();

链表的具体基本操作 文件名(List.c)

链表的初始化及销毁

#include "List.h"
void ListInit(ListNode **Node)
{
	assert(Node != NULL);
	*Node = NULL;
}

void ListDestroy(ListNode **Node)
{
	*Node = NULL;
}

链表结点的创建

static ListNode * CreateNode(DataType data)
{
	ListNode *newNode = (ListNode *)malloc(sizeof(ListNode));
	assert(newNode);
	newNode->data = data;
	newNode->next = NULL;
	
	return newNode;
}

头插法

//头插
void ListPushFront(ListNode **Node,DataType data)
{
	//assert(Node != NULL);

	ListNode *newNode = CreateNode(data);		 // *newNode 用来存储新结点的地址	
	newNode->next = *Node;						 // 把头结点的地址赋给新结点 

	*Node = newNode;							// 把新结点的地址赋给头结点 （ *Node用来存储下一个结点的地址）
	
}

尾插法

//尾插
void ListPushBack(ListNode **Node,DataType data)
{
	ListNode *newNode = CreateNode(data);

	ListNode *cur = *Node;								//把头结点地址赋给cur

	if (*Node == NULL)									//判断头结点是否为空，如果为空，将新的结点赋给头结点（如果是空链表）
	{
		*Node = newNode;
		return;
	}

	while (cur->next !=NULL)							//如果头结点不为空，则将判断头结点指向下一个结点以及后面的结点是否为空
	{													// 如果有空结点，则将赋给当前cur，
		cur = cur->next;
	}
	cur->next = newNode;								//将新的结点地址赋给当前的下一结点
}

头结点的删除

void ListPopFront(ListNode **Node)
{
	//assert(Node != NULL);
	//assert(*Node != NULL);
	
	ListNode *del = *Node;								// 将头结点的地址del，然后指向下一个结点并赋给Node，然后释放del（头结点存储在del中）

	*Node = del->next;
	free(del);
}

尾结点的删除

void ListPopBack(ListNode **Node)
{
	/*ListNode *del = *Node ;
	while (del->next != NULL)
	{
		del = del->next;
	}
	*Node = del->next; 

	free(del);*/


	ListNode *del;
	ListNode *cur = *Node;

	while (cur->next->next != NULL)			// cur->next->next :头指针指向头结点，然后指向下一个结点
	{										// 判断并找到最后一个结点的地址，赋给del					
		cur = cur->next;
	}

	del = cur->next;
	cur->next = NULL;
	free(del);
}

查找

//查找
ListNode* ListFind(ListNode *Node , DataType data)
{
	ListNode *cur;
	for (cur = Node;cur != NULL;cur=cur->next)
	{
		if (data == cur->data)
		{
			return cur;
		}
	}
	return NULL;
}

结点前插入

//在某结点前插入结点
void ListInsert(ListNode **Node,ListNode *pos,DataType data)
{
	ListNode *cur = *Node;
	ListNode *newNode;
	if (*Node == pos)
	{
		ListPopFront(Node);
		return;
	}
	
	
	while (cur->next != pos)
	{
		cur = cur->next;
	}

	newNode = CreateNode(data);
	newNode->next = cur->next;
	cur->next =newNode;

}

删除指定结点

//删除指定结点
void ListDelete(ListNode **Node,ListNode *pos)
{
	ListNode *cur = *Node;
	if (*Node == pos)
	{
		ListPopFront(Node);
	}
	while (cur->next != pos)
	{
		cur = cur->next;
	}

	cur->next = pos->next;
	free(pos);
}

单链表的打印

//单链表的打印
void  ListPrint(ListNode *Node)
{
	ListNode *cur = Node;
	if (Node == NULL)
	{
		return;
	}

	while (cur != NULL)
	{
		printf("%d--> ",cur->data);
		cur = cur->next;
	}	
}