devbox
爱喝兽奶帝天荒
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构基础（链表）_数据结构基础 链表

作者：爱喝兽奶帝天荒 | 2024-07-10 17:02:19

赞

踩

数据结构基础 链表

链表的定义：

  1. typedef int DataType;
  2.  
  3. typedef struct ListNode
  4. {
  5.         Datatype data;
  6.         struct ListNode* next;
  7. }ListNode;

递归实现链表的逆序打印

 

  1. void Reverse(ListNode *pList)//递归实现逆序打印
  2. {
  3.         if(pList == NUll)
  4.         {
  5.                 return;
  6.         }
  7.         else if(pList != NULL)
  8.         {
  9.                 Reverse(pList->next);
  10.                 printf("%d-->",pList->data);
  11.         }
  12. }

删除无头结点的非尾节点

 

 

  1. void RemoveNotHead(ListNode **ppList,Datatype x)//删除无头链表的非尾节点
  2. {
  3.         ListNode *del = NULL;
  4.         ListNode *cul = Find(*ppList,x);
  5.         assert(ppList);
  6.         if(cur==NULL)
  7.         {
  8.                 return
  9.         }
  10.         del = cur->next;
  11.         cur->data = del->data;
  12.         cur->next = del->next;
  13.         free(del);
  14. }

 在无头单链表的一个节点前插入一个节点

  1. void InsertNonFront(ListNode *pos,DataType x)//在无头单链表的一个节点前
  2. 插入一个节点
  3. {
  4.         ListNode *cur = pos->next;
  5.         ListNode *tmp = BuyNode(x);
  6.         DataType _tmp;
  7.         assert（pos);
  8.         pos->next = tmp;
  9.         tmp->next = cur;
  10.         _tmp = pos->data;
  11.         pos->next = tmp->data;
  12.         tmp->data = -tmp;
  13.  
  14. }

逆置单链表

 

 

  1. ListNode *_Reverse(ListNode *pList)//逆转链表
  2. {
  3.         ListNode *NewList = NUll;
  4.         ListNode *cur = pList;
  5.         while(cur)
  6.         {
  7.                 //1.摘节点
  8.                 ListNode *tmp = cur;
  9.                 cur = cur->next;
  10.                 //2.头插
  11.                 tmp->next = NewList;
  12.                 NewList = tmp;
  13.         }
  14.         return NewList;
  15. }

约瑟夫环

 

  1.  ListNode *JosephRing(ListNode *list,int k)
  2.  {
  3.          ListNode *cur = list;
  4.          int count = k;
  5.          ListNode *Next = cur->next;
  6.          if(list == NULL)
  7.          {
  8.                  return;
  9.          }
  10.          while(cur->next!=cur)
  11.          {
  12.                  while(--count)
  13.                  {
  14.                          cur = cur->next;
  15.                  }
  16.                  cur->data = Next->data;
  17.                  cur->next = Next->next;
  18.                  free(next);
  19.          }
  20.          return cur;
  21.  }

 链表的冒泡排序

  1. void BubbleSortList(ListNode *pList)//对链表进行冒泡排序
  2. {
  3.         ListNode *cur = plist;
  4.         ListNode *tail = NUll;
  5.         if((cur == NUll)||(cur->next == NUll))
  6.         {
  7.                 return;
  8.         }
  9.         while(cur->next!=tail)//总趟数
  10.         {
  11.                 while(cur->next!=tail)
  12.                 {
  13.                         if((cur->data) > (cur->next->data))
  14.                         {
  15.                                 DataType tmp = cur->data;
  16.                                 cur->data = cur->next->data;
  17.                                 cur->next->data = tmp;
  18.                         }
  19.                         cur = cur->next;
  20.                 }
  21.                 tail = cur;
  22.                 cur = pList;
  23.         }
  24. }

 找中间节点

 

  1.  ListNode *FindMidNode(ListNode *pList)//找中间节点
  2.  {
  3.          ListNode *fast = pList;
  4.          ListNode *slow = pList;
  5.          if(pList == NULL)
  6.          {
  7.                  return;
  8.          }
  9.          while(fast!=NULL&&fast->next!=NUll)
  10.          {
  11.                  fast = fast->next->next;//双指针，快指针走两步，慢指针走一步
  12.                  slow = slow->next;
  13.          }
  14.          return slow;
  15.  }

有序合并

 

  1.  ListNode *Merge(ListNode *ppl1,ListNode *ppl2)//有序链表合并
  2.  {
  3.          ListNode *head = NULL;
  4.          ListNode *cur = NULL;
  5.          assert(ppl2!=NULL);
  6.          assert(ppl1!=NULL);
  7.  
  8.          if((*ppl1)->data<(*ppl2)->data)
  9.          {
  10.                  head = *ppl1;
  11.                  cur = head;
  12.                  *ppl1 = (*ppl1)->next;
  13.          }else
  14.          {
  15.                  head = *ppl2;
  16.                  cur = head;
  17.                  *ppl2 = (*ppl2)->next;
  18.          }
  19.          while((*ppl11=NULL)&&(*ppl2!=NULL))
  20.          {
  21.                  if((*ppl1)->data<(*ppl2)->data)
  22.                  {
  23.                          cur->next = *ppl1;
  24.                          *ppl1 = (*ppl1)->next;
  25.                  }
  26.                  else
  27.                  {
  28.                          cur->next = *ppl2;
  29.                          *ppl2 = (*ppl2)->next;
  30.                  }
  31.                  cur = cur->next;
  32.          }
  33.          if(*ppl1!=NULL)
  34.          {
  35.                  cur->next = *ppl1;
  36.          }
  37.          else if(*ppl2!=NULL)
  38.          {
  39.                  cur->next = *ppl2;
  40.          }
  41.          return head;
  42.  }

 判断链表是否有环

  1. ListNode *IsCycle(ListNode *pList)//判断是否带环
  2. {
  3.         ListNode *slow = pList;
  4.         ListNode *fast = pList;
  5.         while(fast&&fast->next)
  6.         {
  7.                 slow = slow->next;
  8.                 fast = fast->next->next;//快指针走两步，慢指针走一步
  9.                 if(fast==slow) return fast;//若存在环则两指针会相遇
  10.         }
  11.         return NULL;
  12. }

求环的长度

  1. int GetCycleLength(ListNode *Meet)//求环长度
  2. {
  3.         ListNode *meet = NULL;
  4.         int count = 0;
  5.         if(Meet == NULL)
  6.         {
  7.                 return count;
  8.         }
  9.         meet = IsCycle(Meet);
  10.         Meet = meet;
  11.         meet = meet->next;
  12.         count++;
  13.         while(meet != Meet)//从相遇节点开始，知道下次相遇即为环的长度
  14.         {
  15.                 count++;
  16.                 meet = meet->next;
  17.         }
  18.         return count;
  19. }

求环的入口

 定义两个指针，一个指针从链表开始出发，另一个指针从相遇点出发，两个指针再次相遇的点就是入口点

  1. ListNode *GetCircleEntryNode(ListNode *meet,ListNode *plist)//求环的入口点
  2. {
  3.         ListNode *first = meet;
  4.         ListNode *second = plist;
  5.         if((plist == NULL)||(meet == NULL))//一个指针从链表开始，另一个从相遇点出发，两个指针再次相遇的点就是入口点
  6.                 return NULL;
  7.  
  8.         while(first != second)
  9.         {
  10.                 first = first->next;
  11.                 second = second->next;
  12.         }
  13.         return first;
  14. }

 判断两个环是否相交

先比较两个链表，找出长链表，定义两个指针，先让一个指针从长链表走相差步，另一个指针再从短链表走，当两个链表同时指向同一个节点，带节点为相交点

  1. ListNode *GetCrossNode(ListNode *l1,ListNode *l2)//判断两环是否相交
  2. {
  3.         int len1 = 0;
  4.         int len2 = 0;
  5.         ListNode *cur1 = l1;
  6.         ListNode *cur2 = l2;
  7.         ListNode *shortlist,*longlist;
  8.         if(cur == NULL||cur1 == NULL)
  9.                 return NULL;
  10.         while(cur1)
  11.         {
  12.                 len1++;
  13.                 cur1 = cur1->next;
  14.         }
  15.         while(cur2)
  16.         {
  17.                 len2++;
  18.                 cur2 = cur2->next;
  19.         }
  20.         shortlist = l2;
  21.         longlist = l1;
  22.         if(len2 > len1)
  23.         {
  24.                 shortlist = l1;
  25.                 longlist = l2;
  26.         }
  27.  
  28.         int gap = abs(len1-len2);
  29.         while(gap--)
  30.         {
  31.                 longlist = longlist->next;
  32.         }
  33.         while(shortlist != longlist)
  34.         {
  35.                 shortlist = shortlist->next;
  36.                 longlist = longlist->next;
  37.         }
  38. }

删除倒数第K个数

 

  1. void DelLinkList(ListNode *pList, int k)//删除倒数第K个节点
  2. {
  3.         ListNode *fast = pList;
  4.         ListNode *slow = pList;
  5.         ListNode *Del = NULL;
  6.         if(pList == NULL)return;
  7.         while((fast != NULL)&&(fast->next != NULL))
  8.         {
  9.                 while(--k>0)
  10.                 {
  11.                         Del = fast;//fast先走K步之后slow走，直达fast走到链表结尾
  12.                         fast = fast->next;
  13.                 }
  14.                 fast = fast->next;
  15.                 slow = slow->next;
  16.         }
  17.         Del = slow->next;
  18.         slow->data = Del->data;
  19.         slow->next = Del->next;
  20.         free(Del);
  21.         Del = NULL;
  22. }

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/爱喝兽奶帝天荒/article/detail/806988
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号