本篇文章的代码是在上一篇代码的基础上，
实现了链表的合并；
实现了约瑟夫环；
并且判断两条链表是否有交点等功能；
检查链表是否为环，若是环又如何去计算环的长度以及查找环的入口；
查找环的入口思路如图示：
要实现的接口如下：
#ifndef _SLIST_H__ #define _SLIST_H__ #include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int DataType; typedef struct Node { DataType data; struct Node *next; }Node,*pNode,*pList; pNode BuyNode(DataType d); void InitList(pList* pplist); void PrintfList(pList plist); void PushBack(pList* pplist,DataType d); void PopBack(pList* pplist); pNode FindMidNode(pList plist); void DelKNode(pList *plist, int k); int GetLength(pList plist); pNode Find(pList plist, DataType d); void ReversePrint(pList plist); pList MergeList(pList plist1, pList plist2); pNode CheckCycle(pList cplist); int GetCycleLength(pNode meet); pNode GetCycleEnter(pList plist, pNode meet); int CheckCross(pList plist1, pList plist2); pNode JosephCycle(pList *pplist, int num); #endif
基本函数接口的实现：
#include "SList.h" void InitList(pList* pplist) { assert(pplist); *pplist = NULL; } pNode BuyNode(DataType d) { pNode newnode = (pNode)malloc(sizeof(Node)); if (newnode == NULL) { perror("malloc"); return NULL; } newnode->data = d; newnode->next = NULL; return newnode; } void PrintfList(pList plist) { pNode cur = plist; if (plist == NULL) { printf("列表为空\n"); return; } while (cur) { printf("%d->", cur->data); cur = cur->next; } printf("NULL\n"); } void PushBack(pList* pplist, DataType d) { assert(pplist); pNode pNewNode = BuyNode(d); if (*pplist == NULL) { *pplist = pNewNode; } else { pNode cur = *pplist; while (cur->next) { cur = cur->next; } cur->next = pNewNode; } } void PopBack(pList* pplist) { assert(pplist); pNode cur = *pplist; if (cur == NULL) { printf("列表为空\n"); return; } if (cur->next == NULL) { *pplist = NULL; printf("删除成功\n"); return; } while (cur->next->next) { cur = cur->next; } pNode del = cur->next; cur -> next = NULL; free(del); printf("删除成功\n"); } pNode FindMidNode(pList plist) //找中间结点 { pNode fast = plist; pNode slow = plist; if (plist == NULL) { return NULL; } while (fast&&fast->next) { fast = fast->next->next; slow = slow->next; } return slow; } void DelKNode(pList *pplist, int k) //删除倒数第K个结点（K>1&&K<链表的总长度） { assert(pplist); if (k<=1 || k>=GetLength(*pplist)) { printf("输入不合法\n"); return; } pNode fast = *pplist; pNode slow = *pplist; while (fast->next) { fast = fast->next; k--; if (k < 0) { slow = slow->next; } } pNode del = slow->next; slow->next = slow->next->next; free(del); printf("删除成功\n"); } int GetLength(pList plist) { pNode cur = plist; int count = 0; if (plist == NULL) { return -1; } while (cur) { cur = cur->next; count++; } return count; } pNode Find(pList plist, DataType d) { pNode cur = plist; while (cur) { if (cur->data == d) return cur; else cur = cur->next; } return NULL; }
逆序打印采用的是递归调用：
void ReversePrint(pList plist) { pNode cur = plist; if (plist == NULL) { return; } if (cur->next) { ReversePrint(cur->next); } printf("%d->", cur->data); }
合并两条链表的关键是确定新链表的头结点，再将两条链表的结点按大小顺序插入到头结点后面。
pList MergeList(pList plist1, pList plist2) { pList newlist = NULL; pNode tail = NULL; if (plist1 == plist2) //两条链表相同 return plist1; if (plist1 == NULL) //一条链表为空 return plist2; if (plist2 == NULL) return plist1; if (plist2->data <= plist2->data) //确定头结点 { newlist = plist1; plist1 = plist1->next; } else { newlist = plist2; plist2 = plist2->next; } tail = newlist; while (plist1 != NULL&&plist2 != NULL) { if (plist1->data <= plist2->data) { tail->next = plist1; tail = plist1; plist1 = plist1->next; } else { tail->next = plist2; tail = plist2; plist2 = plist2->next; } } if (plist1 == NULL) { tail->next = plist2; return newlist; } else { tail->next = plist1; return newlist; } }
定义一个快指针，一个慢指针，同时出发，如果快指针和慢指针在某一点相遇，则该链表带环，否则不带。
pNode CheckCycle(pList cplist) //检查是否为环，若是，则返回相遇结点 { pNode fast = cplist; pNode slow = cplist; while (fast&&fast->next) { fast = fast->next->next; slow = slow->next; if (fast == slow) { return slow; } } return NULL; } int GetCycleLength(pNode meet) //计算环的长度 { int count = 0; pNode cur = meet; do { count++; cur = cur->next; } while (cur != meet); return count; }
思路如上图所示：
pNode GetCycleEnter(pList plist, pNode meet) //寻找环的入口 { pNode pline = plist; pNode pcycle = meet; while (pline != pcycle) { pline = pline->next; pcycle = pcycle->next; } return pline; }
如果两条链表的尾结点相同，则有交点，否则没有：
int CheckCross(pList plist1, pList plist2) //判断两条链表是否相交 { pNode cur1 = plist1; pNode cur2 = plist2; if ((cur1 == NULL) || (cur2 == NULL)) { return -1; } while (cur1->next) { cur1 = cur1->next; } while (cur2->next) { cur2 = cur2->next; } if (cur1 == cur2) { return 1; } else { return -1; } }
约瑟夫环问题：
pNode JosephCycle(pList *pplist, int num) //约瑟夫环 { assert(pplist); pNode cur = *pplist; while (1) { if (cur->next == cur) { printf("%d\n", cur->data); break; } int i = 0; for (i = 0; i < num - 1; i++) { cur = cur->next; } printf("%d->", cur->data); pNode del = cur->next; cur->data = cur->next->data; cur->next = cur->next->next; free(del); } return cur; }
测试文件：
#define _CRT_SECURE_NO_DEPRECATE #include "SList.h" void menu() { printf("\n"); printf("*************** 单链表 **************\n"); printf(" 0.Exit 1.PrintfList \n"); printf(" 2.PushBack 3.PopBack \n"); printf(" 4.FindMidNode 5.DelKNode \n"); printf(" 6.GetLength 7.Find \n"); printf(" 8.ReversePrint 9.MergeList \n"); printf(" 10.CheckCycle 11.GetCycleLength\n"); printf(" 12.GetCycleEnter 13.CheckCross \n"); printf(" 14.JosephCycle \n"); } void text1() { pList plist1 = NULL; pList plist2 = NULL; PushBack(&plist1, 1); PushBack(&plist1, 3); PushBack(&plist1, 7); PushBack(&plist1, 8); PushBack(&plist2, 2); PushBack(&plist2, 5); PushBack(&plist2, 9); PushBack(&plist2, 10); PrintfList(plist1); PrintfList(plist2); pList pret = MergeList(plist1, plist2); PrintfList(pret); } void text2() { pList plist1 = NULL; pList plist2 = NULL; PushBack(&plist1, 1); PushBack(&plist1, 3); PushBack(&plist1, 7); PushBack(&plist1, 8); PushBack(&plist2, 2); PushBack(&plist2, 5); PushBack(&plist2, 9); PushBack(&plist2, 10); Find(plist1,8)->next = Find(plist2, 9); int ret = CheckCross(plist1, plist2); if (ret == -1) { printf("无交点\n"); } else { printf("有交点\n"); } } void text() { int input = 0; pList plist = NULL; InitList(&plist); pList cplist = NULL; InitList(&cplist); PushBack(&cplist, 1); PushBack(&cplist, 2); PushBack(&cplist, 3); PushBack(&cplist, 4); PushBack(&cplist, 5); PushBack(&cplist, 6); PushBack(&cplist, 7); PushBack(&cplist, 8); PushBack(&cplist, 9); Find(cplist, 9)->next = Find(cplist, 4); do { DataType data = 0; pNode pret = NULL; pNode enter = NULL; int k = 0; int ret = 0; int clength = 0; menu(); printf("请选择："); scanf("%d", &input); switch (input) { case 0: break; case 1: PrintfList(plist); break; case 2: printf("请输入要插入的数："); scanf("%d", &data); PushBack(&plist,data); printf("插入成功\n"); break; case 3: PopBack(&plist); break; case 4: pret = FindMidNode(plist); if (pret==NULL) printf("列表为空\n"); else printf("中间结点为 %d\n", pret->data); break; case 5: if (plist == NULL) printf("当前列表为空\n"); else { printf("请输入要删除的倒数K结点："); scanf("%d", &k); DelKNode(&plist, k); } break; case 6: ret = GetLength(plist); if (ret == -1) printf("当前列表为空\n"); else printf("当前列表长度为%d", ret); case 7: printf("请输入要查找的数:"); scanf("%d", &data); pret = Find(plist, data); if (pret == NULL) printf("当前列表中无该元素\n"); else printf("%d", pret->data); break; case 8: ReversePrint(plist); printf("NULL"); break; case 9: text1(); break; case 10: pret = CheckCycle(cplist); if (pret == NULL) printf("没有环\n"); else printf("有环，并且相遇结点是%d", pret->data); break; case 11: pret = CheckCycle(cplist); clength = GetCycleLength(pret); printf("%d", clength); break; case 12: pret = CheckCycle(cplist); enter = GetCycleEnter(cplist, pret); printf("%d", enter->data); break; case 13: text2(); break; case 14: Find(cplist, 9)->next = cplist; pNode ret = JosephCycle(&cplist, 3); printf("%d\n", ret->data); break; default: printf("输入错误，请重新输入\n"); break; } } while (input); } int main() { text(); return 0; }