C语言单链表插入/删除/查找/遍历/递归/合并/排序

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。

1 链表结构

2 链表操作

链表操作难度不大，只要我们熟悉其数据结构，说白了就是操作指针。下面附上我对单链表的相关操作的代码

先看头文件如下：

#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>

//typedef int DataType;

//定义链表节点
typedef struct node
{
	int data;   //链表数据
	struct node* pNext; //链表下个节点

}Node, *pNode;

//创建节点
pNode CreateNode(int data );
//遍历链表
void travelList(pNode pHead);
//尾插法
void pushBack(pNode* pHead, int data);
//尾删法
void popBack(pNode* pHead);
//头插法
void pushFront(pNode* pHead, int data);
//头删法
void popFront(pNode* pHead);
//清空链表
void destoryList(pNode pHead);
//获取链表长度
int getListSize(pNode pHead);
//查找节点
pNode findNode(pNode pHead, int data);
//在某位置后插入数据
void insertNode(pNode pPos, int data);
//删除某位置的数据根据节点数据
void deleteNode_bydata(pNode* pHead, int data);
//删除某位置的数据节点指针
void deleteNode_bydata(pNode* pHead, pNode pos);
//查找中间节点
pNode findMidNode(pNode pHead);
//查找倒数第k个节点(要求只能遍历一次)
pNode findKNode(pNode pHead,int k);
//倒着打印单链表（递归）
void travelList_TailtoHead(pNode pHead);

// 将原链表逆置
void reverse(pNode* pHead);
//合并两个有序链表（递归）
pNode mergetwoList(pNode pHead1, pNode pHead2);
//冒泡排序
void sortList(pNode pHead);

再看cpp文件

#include "singlelist.h"

//创建单节点，并返回节点结构
pNode CreateNode(int data )
{
	pNode pTemp = (pNode)malloc(sizeof(Node));
	pTemp->data = data;
	pTemp->pNext = NULL;
	return pTemp;
}
//遍历链表
void travelList(pNode pHead)
{
	pNode pTemp = pHead;
	printf("list data is: ");
	while (pTemp)
	{
		printf("%d  ", pTemp->data);
		pTemp = pTemp->pNext;
	}

	printf("\n");
}
//尾插法
void pushBack(pNode* pHead, int data)
{
	if(*pHead == NULL)
	{
		*pHead = CreateNode(data);
	}
	else
	{
		pNode pTemp = *pHead;
		//找到最后一个存在的节点
		while(pTemp->pNext != NULL)
		{
			pTemp = pTemp->pNext;			
		}
		pTemp->pNext = CreateNode(data);
	}
}
//尾删法
void popBack(pNode* pHead)
{
	if(pHead == NULL)
		return;
	else if((*pHead)->pNext == NULL)
	{
		free(*pHead);
		*pHead = NULL;
		return;
	}
	else
	{
		pNode pTemp = *pHead;
		pNode pPrev = NULL;
		while (pTemp->pNext != NULL)
		{
			pPrev = pTemp;
			pTemp = pTemp->pNext;
		}
		free(pTemp);
		pPrev->pNext = NULL;

	}
}

//头插法 生成一个新的节点，然后将节点插入到当前链表的表头，即头结点之后
void pushFront(pNode* pHead, int data)
{
	if(*pHead == NULL)
	{
		*pHead = CreateNode(data);
	}
	else
	{
		pNode pTemp = CreateNode(data);
		pTemp->pNext = *pHead;
		
		(*pHead) = pTemp;		
	}
}
//头删法删除表头第一个节点
void popFront(pNode* pHead)
{
	if (*pHead == NULL)
	{
		return;
	}
	else if ((*pHead)->pNext == NULL)
	{
		free(*pHead);
		*pHead = NULL;
	}
	else
	{
		pNode pTemp = *pHead;
		*pHead = (*pHead)->pNext;
		free(pTemp);
	}
}
//清空链表
void destoryList(pNode pHead)
{
	pNode pCur = pHead;
	while (pCur)
	{
		pNode pTemp = pCur;
		pCur = pCur->pNext;
		free(pTemp);
	}
	pHead = NULL;
}
//获取链表长度
int getListSize(pNode pHead)
{
	int count=0;
	if (pHead == NULL)
	{
		return 0;
	}
	else
	{
		pNode pTemp = pHead;
		while (pTemp)
		{
			count++;
			pTemp = pTemp->pNext;
		}
		return count;
	}
}

//查找节点
pNode findNode(pNode pHead, int data)
{
	pNode pTemp = pHead;
	while(pTemp)
	{
		if(pTemp->data == data)
			return pTemp;

		pTemp = pTemp->pNext;
	}

	return NULL;
}
//在某位置后插入数据
void insertNode(pNode pPos, int data)
{
	if (pPos == NULL)
	{
		return;
	}
	else
	{
		pNode pTemp = CreateNode(data);
		pTemp->pNext = pPos->pNext;
		pPos->pNext = pTemp;
	}
}

//删除某位置的数据按照数据查找删除
void deleteNode_bydata(pNode* pHead, int data)
{
	if (*pHead == NULL)
	{
		return;
	}
	else if((*pHead)->data == data)
	{
		pNode pTemp = *pHead;
		*pHead = pTemp->pNext;
	
		free(pTemp);
	}
	else
	{
		pNode pTemp = *pHead;
		while (pTemp)
		{	
			if(pTemp->pNext->data == data)
			{				
				pNode pCur = pTemp->pNext->pNext;
				free(pTemp->pNext);
				pTemp->pNext = pCur;
				break;
			}	
			pTemp = pTemp->pNext;
		}
	}
}
//删除某位置的数据按照节点查找删除
void deleteNode_bydata(pNode* pHead, pNode pos)
{
	if (*pHead == pos)
	{
		if ((*pHead)->pNext != NULL)
		{
			pNode pTemp = *pHead;
			*pHead = (*pHead)->pNext;
			free(pTemp);
		}
		else
		{
			free(*pHead);
			*pHead = NULL;
		}
		
		return;
	}
	else
	{
		pNode pPrev = *pHead;
		while (pPrev)
		{
					
			if(pPrev->pNext == pos)
			{
				pPrev->pNext = pos->pNext;
				free(pos);
				break;
			}

			pPrev = pPrev->pNext;
		}
	}
}
//查找中间节点 通过一个2倍步长指针和单倍步长的指针，实现查找中间节点，
pNode findMidNode(pNode pHead)
{
	pNode fast = pHead;
	pNode slow = pHead;
	while (fast && fast->pNext)
	{
		fast = fast->pNext->pNext;
		slow = slow->pNext;
	}
	return slow;
}

//查找倒数第k个节点(要求只能遍历一次)通过两个指针查找次数和来计算出倒数的位置处的节点
pNode findKNode(pNode pHead,int k)
{
	pNode fast = pHead;
	pNode slow = pHead;

	while(fast && k--)
	{
		fast = fast->pNext;
	}
	if(k>0) //防止传入的位置与实际链表长度不符合
	{
		return NULL;
	}
	while (fast)
	{
		slow = slow->pNext;
		fast = fast->pNext;
	}

	return slow;
}
//倒着打印单链表（递归）
void travelList_TailtoHead(pNode pHead)
{
	if (pHead)
	{
		travelList_TailtoHead(pHead->pNext);
		printf(" %d ", pHead->data);
	}

}

// 将原链表逆置将原始的数据依次采用头插法实现逆置
void reverse(pNode* pHead)
{
	pNode cur = *pHead;
	pNode newHead = NULL;
	while (cur)
	{
		pNode pTemp = cur;
		cur = cur->pNext;
		pTemp->pNext = newHead;
		newHead = pTemp;
	}

	*pHead = newHead;
}
//合并两个有序链表（合并后依然有序）（递归）
pNode mergetwoList(pNode pHead1, pNode pHead2)
{
	if(pHead1 == NULL)
	{
		return pHead2;
	}
	else if (pHead2 == NULL)
	{
		return pHead1;
	}

	pNode pMergeHead = NULL;

	if (pHead1->data < pHead2->data)
	{
		pMergeHead = pHead1;
		pMergeHead->pNext = mergetwoList(pHead1->pNext, pHead2);
	}
	else 
	{
		pMergeHead = pHead2;
		pMergeHead->pNext = mergetwoList(pHead2->pNext, pHead1);
	}

	return pMergeHead;
}

//冒泡排序
void sortList(pNode pHead)
{
	if (pHead == NULL)
	{
		return;
	}

	int size = getListSize(pHead);

	for (int i=0;i<size;i++)
	{
		pNode left = pHead;
		pNode right = pHead->pNext;
		for (int j=0;j<size-i-1;j++)
		{
			if(left->data > right->data) //交换位置
			{
				int tmp = left->data;
				left->data = right->data;
				right->data = tmp;
			}

			right = right->pNext;
			left  = left->pNext;
		}
	}
}

最后再看测试代码main.cpp


#include <stdlib.h>
#include <stdio.h>
#include "singlelist.h"

void test1()
{
	pNode singlelist = NULL;
	//尾插
	pushBack(&singlelist, 1);
	pushBack(&singlelist, 2);
	pushBack(&singlelist, 3);
	pushBack(&singlelist, 4);
	pushBack(&singlelist, 5);
	pushBack(&singlelist, 6);
	pushBack(&singlelist, 7);
	travelList(singlelist);
	//尾删
	popBack(&singlelist);
	travelList(singlelist);

	//头插法
	pushFront(&singlelist, 9);
	travelList(singlelist);

	//头删法
	popFront(&singlelist);
	travelList(singlelist);

	//
	destoryList(singlelist);

}

void test2()
{
	pNode singlelist = NULL;
	pushBack(&singlelist, 5);
	pushBack(&singlelist, 6);
	pushBack(&singlelist, 7);
	pushBack(&singlelist, 2);
	travelList(singlelist);
	//查找节点
	pNode pos = findNode(singlelist, 5);
	insertNode(pos, 8);
	travelList(singlelist);
	//根据数据删除节点
	deleteNode_bydata(&singlelist, 5);
	travelList(singlelist);
	//根据位置删除节点
	deleteNode_bydata(&singlelist, findNode(singlelist, 2));
	travelList(singlelist);

	destoryList(singlelist);
}

void test3()
{
	pNode singlelist = NULL;
	//尾插
	pushBack(&singlelist, 1);
	pushBack(&singlelist, 2);
	pushBack(&singlelist, 3);
	pushBack(&singlelist, 4);
	pushBack(&singlelist, 5);
	pushBack(&singlelist, 6);
	pushBack(&singlelist, 7);
	travelList(singlelist);
	//查找节点
	pNode tempNode = NULL;
	tempNode = findMidNode(singlelist);
	printf("mid node is = %d\n", tempNode->data);
	tempNode = findKNode(singlelist, 6);
	printf("mid node is = %d\n", tempNode->data);
	printf("list reverse is: ");
	travelList_TailtoHead(singlelist);
	printf("\n");
	//逆置
	reverse(&singlelist);
	travelList(singlelist);


	destoryList(singlelist);
}

void test4()
{
	pNode tempNode = NULL;
	pNode singlelist1 = NULL;
	pNode singlelist2 = NULL;
	//尾插
	pushBack(&singlelist1, 5);
	pushBack(&singlelist2, 22);
	pushBack(&singlelist1, 3);
	pushBack(&singlelist2, 1);
	pushBack(&singlelist1, 15);
	pushBack(&singlelist2, 62);
	pushBack(&singlelist2, 75);
	pushBack(&singlelist2, 33);
	pushBack(&singlelist1, 15);
	pushBack(&singlelist2, 17);
	pushBack(&singlelist1, 69);
	pushBack(&singlelist2, 65);
	travelList(singlelist1);
	travelList(singlelist2);

	tempNode = mergetwoList(singlelist1, singlelist2);
	travelList(tempNode);
	
	sortList(tempNode);
	travelList(tempNode);


	destoryList(tempNode);
}



int main()
{


	test1();
	printf("----------------------------\n");
	test2();
	printf("----------------------------\n");
	test3();
	printf("----------------------------\n");
	test4();
	system("pause");
	return 0;
}

好了，，以上就是全部的单链表的相关操作以及源码，我采用vs2012编译调试，代码是纯C源码，这些代码可能不是最好的，所以如果大家觉得有问题欢迎来电沟通，及时交流和指正。

原文链接：https://blog.csdn.net/HardessGod/article/details/84972279