# 单链表的基本原理

当构建一个线性结构时应满足以下条件
1.唯一的首元素与唯一的尾元素
2.除第一个元素外,其余每个元素只有一个头元素
3.除最后一个元素外,其余每个元素只有一个尾元素
此外,单链表的储存结构的特点是用任意的储存单元来链接储存的数据元素,
每一个链表节点中都存有当前链表节点的`数据`以及下一位链表节点的`地址`
倘若构建一个具有线性结构的单链表时,
应具有以下线性结构的基本功能
1.首部插入
2.尾部插入
3.选择插入
4.长度获取
5.首部弹出
6.尾部弹出
7.元素搜查
8.元素删除
9.选择删除
10.元素排序
11.顺序逆转
12.元素清除
13.空间销毁
等操作。

# 单链表的基本创建 (整型版本)

Link_List_.h(头文件)
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#define DEBUG_INT
#define ElemForm "%d"
typedef int ElemType;
struct Link_Node
{
	ElemType data;
	struct Link_Node* next;
};
struct Link_Pointer
{
	struct Link_Node* head;
	struct Link_Node* tail;
	int size;
};
void Initial_Node(struct Link_Pointer* L_Node);
void push_back(struct Link_Pointer* L_Node, const ElemType data);
void push_front(struct Link_Pointer* L_Node, const ElemType data);
void pop_back(struct Link_Pointer* L_Node);
void pop_front(struct Link_Pointer* L_Node);
void Show_List_Node(const struct Link_Pointer* L_Node);
int get_length(const struct Link_Pointer* L_Node);
struct Link_Node* find(const struct Link_Pointer* L_Node, const ElemType data);
void insert_pos(struct Link_Pointer* L_Node, const ElemType data, const int pos);
void delete_val(struct Link_Pointer* L_Node, const ElemType data);
void delete_pos(struct Link_Pointer* L_Node, const int pos);
void sort(struct Link_Pointer* L_Node, int (*cmp)(void* d1, void* d2));
void reverse(struct Link_Pointer* L_Node);
void clean(struct Link_Pointer* L_Node);
void destroy_space(struct Link_Pointer* L_Node);
Link_List_.c
#include"Link_List_.h"
// 初始化指标
void Initial_Node(struct Link_Pointer* L_Node)
{
	L_Node->size = 0;
	L_Node->head = NULL;
	L_Node->tail = NULL;
}
// 链表末端插入
void push_back(struct Link_Pointer* L_Node, const ElemType data)
{
	// 新链表
	struct Link_Node* P_Node = (struct Link_Node*)malloc(sizeof(struct Link_Node));
	assert(NULL != P_Node);
	P_Node->data = data;
	P_Node->next = NULL;
	if (!(L_Node->size))
	{
		L_Node->head = P_Node;
		L_Node->tail = P_Node;
	}
	else
	{
		L_Node->tail->next = P_Node;
		L_Node->tail = P_Node;
	}
	++L_Node->size;
#ifdef DEBUG_INT
	printf("值%d已插入\n", data);
#endif
#ifdef DEBUG_CHAR
	printf("值%c已插入\n", data);
#endif
}
// 链表前端插入
void push_front(struct Link_Pointer* L_Node, const ElemType data)
{
	struct Link_Node* P_Node = (struct Link_Node*)malloc(sizeof(struct Link_Node));
	assert(NULL != P_Node);
	P_Node->data = data;
	P_Node->next = NULL;
	if (!(L_Node->size))
	{
		L_Node->head = P_Node;
		L_Node->tail = P_Node;
	}
	else
	{
		P_Node->next = L_Node->head;
		L_Node->head = P_Node;
	}
	++L_Node->size;
#ifdef DEBUG_INT
	printf("值%d已插入\n", data);
#endif
#ifdef DEBUG_CHAR
	printf("值%c已插入\n", data);
#endif
}
// 链表末端弹出一位元素
void pop_back(struct Link_Pointer* L_Node)
{
	struct Link_Node* P_Node = L_Node->head;
	if (!(L_Node->size))
		return;
	else if (1 == L_Node->size)
	{
#ifdef DEBUG_INT
		printf("值%d已弹出\n", P_Node->data);
#endif
#ifdef DEBUG_CHAR
		printf("值%c已弹出\n", P_Node->data);
#endif
		free(P_Node);
		L_Node->head = NULL;
		L_Node->tail = NULL;
		--L_Node->size;
	}
	else
	{
		for (; P_Node->next->next; P_Node = P_Node->next)
			;
#ifdef DEBUG_INT
		printf("值%d已弹出\n", P_Node->data);
#endif
#ifdef DEBUG_CHAR
		printf("值%c已弹出\n", P_Node->data);
#endif
		free(P_Node->next);
		P_Node->next = NULL;
		L_Node->tail = P_Node;
		--L_Node->size;
	}
}
// 链表前端弹出一位元素
void pop_front(struct Link_Pointer* L_Node)
{
	if (!(L_Node->size))
		return;
	else if (1 == L_Node->size)
	{
#ifdef DEBUG_INT
		printf("值%d已弹出\n", L_Node->head->data);
#endif
#ifdef DEBUG_CHAR
		printf("值%c已弹出\n", L_Node->head->data);
#endif
		free(L_Node->head);
		L_Node->head = NULL;
		L_Node->tail = NULL;
		--L_Node->size;
	}
	else
	{
		struct Link_Node* P_Node = L_Node->head->next;
#ifdef DEBUG_INT
		printf("值%d已弹出\n", L_Node->head->data);
#endif
#ifdef DEBUG_CHAR
		printf("值%c已弹出\n", L_Node->head->data);
#endif
		free(L_Node->head);
		L_Node->head = P_Node;
		--L_Node->size;
	}
}
// 链表储存空间展示
void Show_List_Node(const struct Link_Pointer* L_Node)
{
	if (!(L_Node->size))
		return;
	else
	{
		struct Link_Node* P_Node = L_Node->head;
		for(;P_Node;P_Node = P_Node->next)
		{
			if (NULL == P_Node->next)
			{
#ifdef DEBUG_INT
				printf("%d->NULL", P_Node->data);
#endif
#ifdef DEBUG_CHAR
				printf("%c->NULL", P_Node->data);
#endif
				break;
			}
#ifdef DEBUG_INT
			printf("%d->", P_Node->data);
#endif
#ifdef DEBUG_CHAR
			printf("%c->", P_Node->data);
#endif
		}
	}
}
// 链表当前空间长度获取
int get_length(const struct Link_Pointer* L_Node)
{
	printf("当前存储空间长度为%d\n", L_Node->size);
	return L_Node->size;
}
// 链表特定元素查找
struct Link_Node* find(const struct Link_Pointer* L_Node, const ElemType data)
{
	if (!(L_Node->size))
		return NULL;
	else
	{
		struct Link_Node* P_Node = L_Node->head;
		int i = 1;
		for(;P_Node;++i)
		{
			if (data == P_Node->data)
			{
#ifdef DEBUG_INT
				printf("值为%d的第一位元素位置为%d\n", data, i);
#endif
#ifdef DEBUG_CHAR
				printf("值为%c的第一位元素位置为%d\n", data, i);
#endif
				return P_Node;
			}
			P_Node = P_Node->next;
		}
		return NULL;
	}
}
// 链表特定元素特定位置的插入
void insert_pos(struct Link_Pointer* L_Node, const ElemType data, const int pos)
{
	if (!(L_Node->size))
		return;
	else if (pos > L_Node->size || pos < 0)
		return;
	else
	{
		if (1 == pos)
			push_front(L_Node, data);
		else if (2 == pos)
		{
			struct Link_Node* E_Node = (struct Link_Node*)malloc(sizeof(struct Link_Node));
			E_Node->data = data;
			E_Node->next = L_Node->head->next;
			L_Node->head->next = E_Node;
			++L_Node->size;
		}
		else
		{
			int e_pos = 2;
			struct Link_Node* P_Node = L_Node->head;
			struct Link_Node* E_Node = (struct Link_Node*)malloc(sizeof(struct Link_Node));
			// 从第 e_pos 位开始找 (n-1) 位
			for(;e_pos < pos;++e_pos)
				P_Node = P_Node->next;
			E_Node->data = data;
			E_Node->next = P_Node->next;
			P_Node->next = E_Node;
			++L_Node->size;
		}
#ifdef DEBUG_INT
		printf("值%d已插入\n", data);
#endif
#ifdef DEBUG_CHAR
		printf("值%c已插入\n", data);
#endif
	}
}
// 链表特定元素的全部删除
void delete_val(struct Link_Pointer* L_Node, const ElemType data)
{
	if (!(L_Node->size))
		return;
	else
	{
		// 头尾删除
		for(;NULL != L_Node->head && data == L_Node->head->data;)
			pop_front(L_Node);
		for(;NULL != L_Node->head && data == L_Node->tail->data;)
			pop_back(L_Node);
		if (!(L_Node->size))
			return;
		// 将后一位的值拷贝后将后一位释放,至少需两位元素
		else
		{
			struct Link_Node* P_Node = NULL;
			struct Link_Node* P_B_Node = NULL;
			for (; P_Node = find(L_Node, data); --L_Node->size)
			{
				P_B_Node = P_Node->next->next;
				P_Node->data = P_Node->next->data;
				free(P_Node->next);
				P_Node->next = P_B_Node;
			}
		}
	}
}
// 链表特定位置删除
void delete_pos(struct Link_Pointer* L_Node, const int pos)
{
	if (!(L_Node->size))
		return;
	else
	{
		if (pos < 0 || pos > L_Node->size)
			return;
		else
		{
			if (1 == pos)
				pop_front(L_Node);
			else if (L_Node->size == pos)
				pop_back(L_Node);
			else
			{
				struct Link_Node* P_B_Node = NULL;
				struct Link_Node* P_Node = L_Node->head;
				int D_Pos = 0;
				for(;D_Pos < pos - 1;++D_Pos)
					P_Node = P_Node->next;
				P_B_Node = P_Node->next->next;
				P_Node->data = P_Node->next->data;
				free(P_Node->next);
				P_Node->next = P_B_Node;
				--L_Node->size;
			}
		}
	}
}
// 链表的万能冒泡排序
void sort(struct Link_Pointer* L_Node, int (*cmp)(void* d1, void* d2))
{
	if (!(L_Node->size))
		return;
	else if (1 == L_Node->size)
		return;
	else
	{
		int i = 0;
		int j = 0;
		for (i = 0; i < L_Node->size; ++i)
		{
			struct Link_Node* P_H_Node = L_Node->head;
			struct Link_Node* P_T_Node = L_Node->head->next;
			for (j = 0; j < L_Node->size - i - 1; ++j)
			{
				int compare = (*cmp)(&P_H_Node->data, &P_T_Node->data);
				if (1 == compare)
				{
					int trans = P_H_Node->data;
					P_H_Node->data = P_T_Node->data;
					P_T_Node->data = trans;
				}
				P_H_Node = P_H_Node->next;
				P_T_Node = P_T_Node->next;
			}
		}
	}
}
// 链表逆序
void reverse(struct Link_Pointer* L_Node)
{
	if (!(L_Node->size))
		return;
	else
	{
		if (1 == L_Node->size)
			return;
		else
		{
			struct Link_Node* P_Head = L_Node->head;
			L_Node->tail = L_Node->head->next;
			L_Node->head->next = NULL;
			for(;L_Node->tail;)
			{
				struct Link_Node* P_Node = L_Node->tail;
				L_Node->tail = P_Node->next;
				P_Node->next = L_Node->head;
				L_Node->head = P_Node;
			}
			L_Node->tail = P_Head;
		}
	}
}
// 清空链表
void clean(struct Link_Pointer* L_Node)
{
	if (!(L_Node->size))
		return;
	else
	{
		int i = L_Node->size;
		for(;i;--i)
			pop_back(L_Node);
	}
}
// 链表当前储存空间摧毁
void destroy_space(struct Link_Pointer* L_Node)
{
	clean(L_Node);
	L_Node->head = NULL;
	L_Node->tail = NULL;
}
Link_List_main.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Link_List_.h"
#define END_F -1
static int cmp(void* d1, void* d2)
{
	ElemType* e1 = (ElemType*)d1;
	ElemType* e2 = (ElemType*)d2;
	if (*e1 > *e2)
		return 1;
	else if (*e1 < *e2)
		return -1;
	else
		return 0;
}
static void Show_Menu()
{
	printf("\n************************************************\n");
	printf(" [1]  push_back      ********[2]  push_front   *\n");
	printf(" [3]  pop_back       ********[4]  pop_front    *\n");
	printf(" [5]  Show_List_Node ********[6]  get_length   *\n");
	printf(" [7]  find           ********[8]  insert_pos   *\n");
	printf(" [9]  delete_val     ********[10] delete_pos   *\n");
	printf(" [11] sort           ********[12] reverse      *\n");
	printf(" [13] clear          ********[14] destroy_space*\n");
	printf(" [0]  quit_system                              *\n");
	printf("************************************************\n");
}
int main()
{
	int option = 0;
	int pos = 0;
	ElemType data = 0;
	struct Link_Pointer LP;
	Initial_Node(&LP);
	Show_Menu();
	while (printf("选择为>:"), scanf("%d", &option), option)
	{
		getchar();// 截取只读缓冲区的换行符
		switch (option)
		{
		case 1:
			printf("插入值为>:");
			while (scanf(ElemForm, &data), END_F != data)
			{
				push_back(&LP, data);
			}
			break;
		case 2:
			printf("插入值为>:");
			while (scanf(ElemForm, &data), END_F != data)
			{
				push_front(&LP, data);
			}
			break;
		case 3:
			pop_back(&LP);
			break;
		case 4:
			pop_front(&LP);
			break;
		case 5:
			Show_List_Node(&LP);
			break;
		case 6:
			get_length(&LP);
			break;
		case 7:
			printf("查找的值为>:");
			scanf(ElemForm, &data);
			find(&LP, data);
			break;
		case 8:
			printf("插入值与位置>:");
			scanf(ElemForm " %d", &data, &pos);
			insert_pos(&LP, data, pos);
			break;
		case 9:
			printf("需要删除的元素值>:");
			scanf(ElemForm, &data);
			delete_val(&LP, data);
			break;
		case 10:
			printf("需要删除的元素位置>:");
			scanf("%d", &pos);
			delete_pos(&LP, pos);
			break;
		case 11:
			sort(&LP, cmp);
			break;
		case 12:
			reverse(&LP);
			break;
		case 13:
			clean(&LP);
			break;
		case 14:
			destroy_space(&LP);
			break;
		default: printf("输入值不在选择范围\n");
		}
		Show_Menu();
	}
	destroy_space(&LP);
	printf("已退出\n");
	return 0;
}

# LeetCode 案题

Merge Two Sorted Lists(合并两个已排序的单链表)
/*
题目
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]
Constraints:
1.The number of nodes in both lists is in the range [0, 50].
2.-100 <= Node.val <= 100
3.Both list1 and list2 are sorted in non-decreasing order.
*/
/*
单链表解法
*/
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* Head = NULL;
    struct ListNode** P_Head = &Head;
    struct ListNode** Node_Next = NULL;
    
    for(;NULL != list1 && NULL != list2;*Node_Next = (*Node_Next)->next)
    {
        Node_Next = (list1->val < list2->val) ? &list1 : &list2;
        *P_Head = *Node_Next;
        P_Head = &(*P_Head)->next;
    }
    *P_Head = (struct ListNode*)((uintptr_t)list1 | (uintptr_t)list2);
    
    return Head;
}

题解出自:→你所不知道的 C 語言: linked list 和非連續記憶體 (强烈推荐阅读)