下面就是我实现的单链表的各个功能的函数，可能会有考虑不周的地方
#include#include #include typedef int DataType; //数据类型重命名typedef struct _node //定义节点结构体{ DataType data; //数据 struct _node* next; //指向下一个节点的指针}ListNode;void InitList(ListNode** phead) //初始化phead{ *phead = NULL;}ListNode* CreatNode(DataType val) //创建一个DataType数据为val的新节点{ ListNode* tmp = (ListNode*)malloc(sizeof(ListNode)); //malloc开辟空间 assert(tmp); //判空 tmp->data = val; tmp->next = NULL; return tmp;}void PushBack(ListNode** phead, DataType x) //尾插一个新的节点{ if (*phead == NULL) //空链表 { *phead = CreatNode(x); } else //非空链表 { ListNode* tail = *phead; while (tail->next) { tail = tail->next; } tail->next = CreatNode(x); }}void ShowList(ListNode* phead) //打印单链表{ if(NULL == phead) //判空 { printf("list is empty!\n"); } ListNode* cur = phead; while (cur) { printf("%d ", cur->data); cur = cur->next; } printf("\n");}void PushHead(ListNode** head, DataType x) //头插一个新节点{ //if (NULL == *head) //空链表 //{ // *head = CreatNode(x); //} //else //非空链表 //{ // ListNode* tmp = CreatNode(x); // tmp->next = *head; // *head = tmp; //} ListNode* tmp = CreatNode(x); //没有分情况，也没有什么问题 tmp->next = *head; *head = tmp;}void PopBack(ListNode** phead) //删除尾部节点{ if (NULL == *phead) //空链表 { printf("list is empty!"); return; } else if (NULL == (*phead)->next) //只有一个节点 { free(*phead); *phead = NULL; //free后置空，防止野指针出现 } else //多个节点 { ListNode* tail = *phead; ListNode* pre = *phead; while (tail->next) //先找到尾节点 { pre = tail; tail = tail->next; } pre->next = NULL; free(tail); }}void PopFront(ListNode** phead) //删除头结点{ if (NULL == *phead) //空链表 { printf("list is empty!"); return; } else //非空链表 { ListNode* tag = *phead; *phead = (*phead)->next; free(tag); }}ListNode* Find(ListNode** phead, DataType x) //链表中寻找data值为x的节点{ ListNode* cur = *phead; while (cur) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL;}void Insert(ListNode* pos, DataType x) //在pos位置进行插入{ assert(pos); ListNode* new_node = CreatNode(x); ListNode* tmp = pos->next; new_node->data = pos->data;//将x赋值给pos->data,将pos->data赋值给pos->data;交换顺序 pos->data = x; pos->next = new_node; new_node->next = tmp;}void InsertFrontNode(ListNode* pos, DataType x) //在pos位置的前面进行插入{ assert(pos); ListNode* tmp = CreatNode(x); tmp->next = pos->next; pos->next = tmp; tmp->data = pos->data; pos->data = x; }void Erase(ListNode** phead, ListNode* pos) //删除pos节点{ assert(pos); if (pos == *phead) //pos是第一个节点 { *phead = (*phead)->next; free(pos); } else //pos是任意节点 { ListNode* cur = *phead; while (cur) { if (cur->next == pos) { cur->next = pos->next; free(pos); break; } cur = cur->next; } }}void DelNonTailNode(ListNode* pos) //删除非尾节点{ assert(pos && pos->next); ListNode* del = pos->next;//将pos->next->data赋值给pos->data，把pos->next free,在串起来 ListNode* tmp = pos->next->next; pos->data = pos->next->data; pos->next = tmp; free(del);}void Remove(ListNode** phead, DataType x) //删除节点data值为x的节点{ ListNode* remv = Find(phead, x); if (remv) { Erase(phead, remv); //调用Erase函数 }}ListNode* Reverse(ListNode* phead) //逆置翻转链表{ ListNode* newHead = NULL; ListNode* cur = phead; while (cur) { ListNode* tmp = cur; //进行摘节点，再进行尾插 cur = cur->next; tmp->next = newHead; newHead = tmp; } return newHead;}void PrintTailtoHead(ListNode* phead) //递归实现从尾到头打印{ if (phead) { PrintTailtoHead(phead->next); printf("%d ", head->data); }}ListNode* FindMid(ListNode* phead) //找链表中间节点并返回{ ListNode* slow = phead; //slow 指针 ListNode* fast = phead; //fast指针 while (fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow;}DataType Find_TheLast_Knode(ListNode* phead, int k) //查找倒数第K个节点，遍历一次{ assert(phead); ListNode* pre = phead; //定义两个指针，分别指向前面和后面 ListNode* aft = phead; int i = 1; while (aft) { if (i <= k) { aft = aft->next; i++; } else { aft = aft->next; pre = pre->next; } } //指针aft和pre保持距离为(k-1)，则遍历完成之后，pre即为倒数第K个节点 if ( i > k && k != 0) //不存在倒数第0个节点 { return pre->data; } else return -1;}void swap(DataType* n, DataType* m) //交换两个数{ DataType tmp = *n; *n = *m; *m = tmp;}void BubbleSort(ListNode** head) //链表的冒泡排序{ assert(head); //一个节点 if (NULL == (*head)->next) { return; } else { while (1) { ListNode* cur = (*head)->next; ListNode* p = *head; int exchange = 0; //进行判断是否发生交换 while (cur) { if (p->data > cur->data) { swap(&(p->data), &(cur->data)); exchange = 1; } cur = cur->next; p = p->next; } if (exchange == 0) //一趟循环结束未发生交换则return，跳出死循环 { return; } } }}ListNode* Merge_List(ListNode* l1, ListNode* l2) //合并两个有序的单链表，仍有序{ if (NULL == l1 || NULL == l2) //判断两个链表是否为空 { return l1 == NULL ? l2 : l1; //返回非空的链表或者空链表 } ListNode* newhead = CreatNode(0); //创建一个头结点，之后再进行free ListNode* l = newhead; ListNode* cur1 = l1; ListNode* cur2 = l2; while (cur1 && cur2) { if (cur1->data > cur2->data) { l->next = cur2; l = l->next; cur2 = cur2->next; } else { l->next = cur1; l = l->next; cur1 = cur1->next; } } l->next= (cur1 == NULL ? cur2 : cur1); ListNode* tmp = newhead; newhead = newhead->next; free(tmp); tmp = NULL; return newhead;}ListNode* Joseph_Cycle(ListNode* head,int k) //约瑟夫环{ if (NULL == head) { printf("list is empty!\n"); return NULL; } ListNode* cur = head; while (cur->next != NULL) { cur = cur->next; } ListNode* tmp = NULL; cur->next = head; cur = head; int count = k; while (1) { count = k; if (cur->next != cur) { while (--count) { cur = cur->next; } tmp = cur->next; cur->data = cur->next->data; cur->next = cur->next->next; free(tmp); } else { cur->next = NULL; return cur; } }}ListNode* CreatCycle(ListNode* phead,int k) //为单链表创造一个环{ if (NULL == phead) //phead为空 { printf("list is empty!\n"); return NULL; } ListNode* pos = Find(&phead, k); if (pos == NULL) { printf("k is error!\n"); } ListNode* pos1 = pos; ListNode* tail = phead; while (tail->next) //找到list的尾节点 { tail = tail->next; } tail->next = pos1; //list的尾节点*next指向pos tail = phead; //cur 指向头结点 return tail;}int IsLoop(ListNode* phead) //判断链表是否有环，有环返回1；否则返回-1；{ if (NULL == phead) { printf("list is empty!\n"); return -1; } ListNode* slow = phead; //快指针 ListNode* fast = phead; //慢指针 while (fast && fast->next) { fast = fast->next->next; //fast = 2*slow slow = slow->next; if (&slow->data == &fast->data) { return 1; } } return -1;}ListNode* MeetNode(ListNode* phead) //返回快慢指针在环中相遇的节点,同时也可以判断是否存在环{ if (NULL == phead) { printf("list is empty!\n"); return -1; } ListNode* slow = phead; //快指针 ListNode* fast = phead; //慢指针 while (fast && fast->next) { fast = fast->next->next; //fast = 2*slow slow = slow->next; if (&slow->data == &fast->data) //if(slow == fast); { return slow; } } return NULL;}int GetLength(ListNode* phead) //求单链表的节点个数{ int count = 0; ListNode* cur = phead; if (NULL == phead) //空表 { return count; } else //非空表 { while (cur) { cur = cur->next; count++; } return count; }}ListNode* GetEnterNode(ListNode* phead) //求有环单链表的环的入口节点{ ListNode* meet = MeetNode(phead); //判断list是否存在环 if (NULL == meet) //没有环的情况 { printf("there is no cycle in the list!\n"); return NULL; } else //有环的情况 { ListNode* tar = meet; ListNode* cur = phead; while (tar != cur) //2*（L + X）=L + X + nC L = nC - X { cur = cur->next; tar = tar->next; } return cur; //返回环入口节点 }}