链表试题算法汇总

1 链表基本操作链表基本操作 typedef struct myLink int data struct myLink next Link 创建链表创建链表 包含头节点包含头节点 int creatLink Link phead int res 0 int num Link ptm Link malloc sizeof Link ptm data 0 phead ptm printf 请输入数据 以请输入数据 以 0 结束 结束 n scanf d while num 0 Link pNew Link malloc sizeof Link if pNew NULL res 1 printf pNew NULL 创建链表失败创建链表失败 error d n res pNew data num ptm next pNew ptm pNew printf 请输入数据 以请输入数据 以 0 结束 结束 n scanf d ptm next NULL return res 打印链表打印链表 int printLink Link pHead int res 0 Link p pHead next if p NULL res 1 printf printfLink err d 链表为空打印失败链表为空打印失败 n res return res while p NULL printf data d n p data p p next return res 插入链表在插入链表在 data x 的前面插入的前面插入 data y int insertLink Link pHead int x int y int res 0 if pHead NULL res 1 printf pHead NULL insertLink err d n res return res Link pNew Link malloc sizeof Link pNew data y Link pPre pHead Link pCurr pHead next int flag 0 while pCurr NULL if pCurr data x flag 1 break pPre pPre next pCurr pCurr next if flag 0 res 2 printf 原链表中没有原链表中没有 d n x return res pNew next pCurr pPre next pNew return res 删除链表中节点删除链表中节点 删除删除 data x 的节点的节点 int deleLink Link pHead int x int res 0 if pHead NULL res 1 printf pHead NULL deleLink error d n res return res Link pPre pHead Link pCurr pHead next int flag 0 while pCurr NULL if pCurr data x flag 1 break pPre pPre next pCurr pCurr next if flag 0 res 2 printf 原链表中没有原链表中没有 d n x return res pPre next pCurr next return res 反转链表反转链表 int revertLink Link pHead int res 0 if pHead NULL pHead next NULL pHead next next NULL res 1 printf pHead NULL revertLink error d n res return res Link pPre pHead next Link pCurr pHead next next Link q NULL while pCurr NULL q pCurr next pCurr next pPre pPre pCurr pCurr q pHead next next NULL pHead next pPre return res 链表排序链表排序 再创建一个空链表再创建一个空链表 从原链表中找到最大值的那个节点从原链表中找到最大值的那个节点 然后往空链表里添加然后往空链表里添加 int sortLink Link pHead Link pHead1 int res 0 Link pNewHead Link malloc sizeof Link pNewHead data 0 Link pNewTail pNewHead if pHead NULL res 1 printf pHead NULL sortLink erro d n res return res 先从原链表里找出最大值的那个节点先从原链表里找出最大值的那个节点 start Link pMax pHead next Link pPre pHead Link pCurr pMax next while pCurr NULL if pCurr data pMax data pPre pMax pMax pCurr pCurr pCurr next pPre next pMax next 让最大的那个节点脱离原链表让最大的那个节点脱离原链表 if pNewHead next NULL pNewHead next pMax pNewTail pMax pMax next NULL else pNewTail next pMax pNewTail pMax pMax next NULL if pHead next NULL 所有的节点都脱离了原链表所有的节点都脱离了原链表 goto sortEnd goto start sortEnd pHead1 pNewHead return res int destoryLink Link pHead int res 0 if pHead NULL res 1 printf pHead NULL 链表为空链表为空 释放内存失败释放内存失败 erro d n res return res Link pt pHead while pt NULL Link tmp pt next free pt pt tmp pHead NULL return res 测试案例测试案例 void main Link pHead NULL int res res creatLink if res 0 printf function creatLink err d n res goto End res printLink pHead if res 0 printf function printLink err d n res goto End printf 在在 3 的前面插入的前面插入 4 n res insertLink pHead 3 4 if res 0 printf function insetrLink err d n res goto End res printLink pHead if res 0 printf function printLink err d n res goto End printf 删除删除 data 4 的节点的节点 n res deleLink pHead 4 if res 0 printf function deleLink err d n res goto End res printLink pHead if res 0 printf function printLink err d n res goto End printf 逆转链表逆转链表 n res revertLink pHead if res 0 printf function revertLink err d n res goto End res printLink pHead if res 0 printf function printLink err d n res goto End printf 从大到小排序链表从大到小排序链表 n Link pHead1 NULL res sortLink pHead if res 0 printf function sortLink err d n res goto End res printLink pHead1 if res 0 printf function printLink err d n res goto End End if pHead NULL res destoryLink if res 0 printf function destoryLink is error d n res return system pause 2 单链表的建立 把 单链表的建立 把 a z 26 个字母插入到链表中 个字母插入到链表中 并且倒叙 还要打印并且倒叙 还要打印 include include include include typedeftypedef structstruct valval charchar data data structstruct valval next next node p node p voidvoid main void main void nodenode p p NULL NULL nodenode q q NULL NULL nodenode head head node node malloc sizeof node malloc sizeof node head datahead data head nexthead next NULL NULL nodenode first first node node malloc sizeof node malloc sizeof node first datafirst data a a first nextfirst next NULL NULL head nexthead next first first p p first first intint longthlongth z z b b intint i i 0 0 whilewhile i i datatemp data b i b i temp datatemp data NULL NULL 开始逆转开始逆转 q q temp temp head nexthead next temp temp temp nexttemp next p p p p q q i i 打印链表打印链表 nodenode tmp tmp head next head next whilewhile tmp tmp NULL NULL printf data cprintf data c tmp data tmp data tmptmp tmp next tmp next 3 约瑟夫问题约瑟夫问题 循环链表循环链表 h 文件文件 ifndef CIRCLELIST H define CIRCLELIST H typedef void CircleList typedef struct tag CircleListNode CircleListNode struct tag CircleListNode CircleListNode next typedef struct tag CircleListNode struct tag CircleListNode next CircleListNode CircleList CircleList Create void CircleList Destroy CircleList list void CircleList Clear CircleList list int CircleList Length CircleList list int CircleList Insert CircleList list CircleListNode node int pos CircleListNode CircleList Get CircleList list int pos CircleListNode CircleList Delete CircleList list int pos add CircleListNode CircleList DeleteNode CircleList list CircleListNode node CircleListNode CircleList Reset CircleList list CircleListNode CircleList Current CircleList list CircleListNode CircleList Next CircleList list endif C 文件文件 include include include circleList h typedef struct tag CircleList CircleListNode header CircleListNode slider int length TCircleList CircleList CircleList Create O 1 TCircleList ret TCircleList malloc sizeof TCircleList if ret NULL return NULL ret length 0 ret header next NULL ret slider NULL return ret void CircleList Destroy CircleList list O 1 if list NULL return free list void CircleList Clear CircleList list O 1 TCircleList sList TCircleList list if sList NULL return sList length 0 sList header next NULL sList slider NULL int CircleList Length CircleList list O 1 TCircleList sList TCircleList list int ret 1 if list NULL return ret ret sList length return ret int CircleList Insert CircleList list CircleListNode node int pos O n int ret 0 i 0 TCircleList sList TCircleList list if list NULL node NULL pos 0 return 1 if ret CircleListNode current CircleListNode sList for i 0 inext NULL i current current next current next 0 号节点的地址号节点的地址 node next current next 1 current next node 2 若第一次插入节点若第一次插入节点 if sList length 0 sList slider node sList length 若头插法若头插法 if current CircleListNode sList 获取最后一个元素获取最后一个元素 CircleListNode last CircleList Get sList sList length 1 last next current next 3 return ret CircleListNode CircleList Get CircleList list int pos O n TCircleList sList TCircleList list CircleListNode ret NULL int i 0 if list NULL pos 0 for i 0 inext ret current next return ret CircleListNode CircleList Delete CircleList list int pos O n TCircleList sList TCircleList list CircleListNode ret NULL int i 0 if sList NULL CircleListNode last NULL for i 0 inext 若删除第一个元素若删除第一个元素 if current CircleListNode sList last CircleListNode CircleList Get sList sList length 1 求要删除的元素求要删除的元素 ret current next current next ret next sList length 判断链表是否为空判断链表是否为空 if last NULL sList header next ret next last next ret next 若删除的元素为游标所指的元素若删除的元素为游标所指的元素 if sList slider ret sList slider ret next 若删除元素后 链表长度为若删除元素后 链表长度为 0 if sList length 0 sList header next NULL sList slider NULL return ret CircleListNode CircleList DeleteNode CircleList list CircleListNode node O n TCircleList sList TCircleList list CircleListNode ret NULL int i 0 if sList NULL CircleListNode current CircleListNode sList 查找查找 node 在循环链表中的位置在循环链表中的位置 i for i 0 ilength i if current next node ret current next break current current next 如果如果 ret 找到 根据找到 根据 i 去删除去删除 if ret NULL CircleList Delete sList i return ret CircleListNode CircleList Reset CircleList list O 1 TCircleList sList TCircleList list CircleListNode ret NULL if sList NULL sList slider sList header next ret sList slider return ret CircleListNode CircleList Current CircleList list O 1 TCircleList sList TCircleList list CircleListNode ret NULL if sList NULL ret sList slider return ret CircleListNode CircleList Next CircleList list O 1 TCircleList sList TCircleList list CircleListNode ret NULL if sList NULL sList slider ret next return ret Main c 文件文件 include include include circlelist h typedef struct Value CircleListNode node int v Va void main CircleList circleList NULL circleList CircleList Create Va v1 v2 v3 v4 v5 v6 v7 v8 v1 v 1 v2 v 2 v3 v 3 v4 v 4 v5 v 5 v6 v 6 v7 v 7 v8 v 8 int res res CircleList Insert circleList CircleListNode res CircleList Insert circleList CircleListNode res CircleList Insert circleList CircleListNode res CircleList Insert circleList CircleListNode res CircleList Insert circleList CircleListNode res CircleList Insert circleList CircleListNode res CircleList Insert circleList CircleListNode res CircleList Insert circleList CircleListNode int len CircleList Length circleList for int i 0 i v CircleList Reset circleList printf n n Va tmp NULL while CircleList Length circleList 0 for int i 1 i v CircleList DeleteNode circleList CircleListNode tmp 删除该节点并让游标删除该节点并让游标 后移后移 CircleList Clear circleList CircleList Destroy circleList system pause 4 有一个数组有一个数组 a 1000 存放存放 0 1000 要求每个二个数删除一 要求每个二个数删除一 个 到末尾是循环至开头继续进行 求最后一个被删除的个 到末尾是循环至开头继续进行 求最后一个被删除的 数的原始下标位置数的原始下标位置 include include usingusing namespacenamespace stdstd structstruct nodenode intint datadata nodenode nextnext intint mainmain nodenode headhead newnew nodenode headhead datadata 0 0 headhead nextnext NULLNULL nodenode p p headhead 创建链表创建链表 forfor intint i i 1 1 i i datadata i i tmptmp nextnext NULLNULL headhead nextnext tmptmp headhead headhead nextnext 把链表的尾和头连上把链表的尾和头连上 创建循环链表创建循环链表 headhead nextnext p p whilewhile p p p p nextnext p p nextnext nextnext p p nextnext nextnext nextnext nextnext p p p p nextnext nextnext coutcout datadata datadata datadata headhead head1head1