链表面试题集合

淡淡的烟草味﹌ 2022-05-09 00:18 271阅读 0赞

链表面试题：

  1. 比较顺序表和链表的优缺点,说说它们分别在什么场景下使用?

    • 顺序表一般用于查找，可随机访问；
    • 链表一般用于增删改，不可随机访问；
    • 如果数据元素不多，两种方式没有太大的差别
    • 如果数据元素不定，建议使用链表
    • 顺序表的CPU高速缓存效率高，而单链表CPU高速缓存效率低。

链表的基本操作如下：

  1. #include "List.h"
  3. void InitLinkList(pList* pplist)
  4. {
  5.     (*pplist) = NULL;
  6. }
  8. pNode BuyNode(DataType d)
  9. {
  10.     pNode newNode = (pNode)malloc(sizeof(Node));
  11.     if (newNode == NULL)
  12.     {
  13.         perror("malldc error");
  14.         exit(EXIT_FAILURE);
  15.     }
  16.     newNode->data = d;
  17.     newNode->next = NULL;
  18.     return newNode;
  19. }
  21. void DestroyLinkList(pList* pplist)
  22. {
  23.     assert(pplist);
  24.     pNode cur = NULL;
  25.     cur = *pplist;
  26.     while (cur)
  27.     {
  28.         pNode del = cur;
  29.         cur = cur->next;
  30.         free(del);
  31.         del = NULL;
  32.     }
  33.     *pplist = NULL;
  34. }
  36. void PushBack(pList* pplist, DataType d)
  37. {
  38.     assert(pplist);
  39.     pNode newNode = BuyNode(d);
  40.     if ((*pplist) == NULL)
  41.     {
  42.         *pplist = newNode;
  43.     }
  44.     else
  45.     {
  46.         pNode cur = NULL;
  47.         cur = *pplist;
  48.         while (cur->next)
  49.         {
  50.             cur = cur->next;
  51.         }
  52.         cur->next = newNode;
  53.     }
  54. }
  56. void PopBack(pList* pplist)
  57. {
  58.     assert(pplist);
  59.     if ((*pplist) == NULL)
  60.     {
  61.         printf("链表为空！\n");
  62.         return;
  63.     }
  64.     else
  65.     {
  66.         pNode cur = NULL;
  67.         pNode del = NULL;
  68.         cur = *pplist;
  69.         del = cur->next;
  70.         while (cur->next->next)
  71.         {
  72.             cur = cur->next;
  73.             del = cur->next;
  74.         }
  75.         cur->next = del->next;
  76.         free(del);
  77.         del = NULL;
  78.     }
  79. }
  81. void PushFront(pList* pplist, DataType d)
  82. {
  83.     pNode newNode = BuyNode(d);
  84.     assert(pplist);
  85.     if ((*pplist) == NULL)
  86.     *pplist = newNode;
  87.     else
  88.     {
  89.         pNode cur = *pplist;
  90.         newNode->next = cur;
  91.         *pplist = newNode;
  92.     }
  93. }
  95. void PopFront(pList* pplist)
  96. {
  97.     assert(pplist);
  98.     if ((*pplist) == NULL)
  99.     {
  100.         printf("链表为空！\n");
  101.         return;
  102.     }
  103.     else
  104.     {
  105.         pNode del = NULL;
  106.         del = *pplist;
  107.         *pplist = (*pplist)->next;
  108.         free(del);
  109.         del = NULL;
  110.     }
  111. }
  113. pNode Find(pList plist, DataType d)
  114. {
  115.     if (plist == NULL)
  116.     {
  117.         printf("链表为空！\n");
  118.         return NULL;
  119.     }
  120.     else
  121.     {
  122.         pNode cur = plist;
  123.         while (cur)
  124.         {
  125.             if (cur->data == d)
  126.             {
  127.                 return cur;
  128.             }
  129.             cur = cur->next;
  130.         }
  131.         return NULL;
  132.     }
  133. }
  135. void Insert(pList* pplist, pNode pos, DataType d)//在指定位置之前插入一个值
  136. {
  137.     assert(pplist);
  138.     assert(pos);
  139.     assert(*pplist);
  140.     pNode newNode = BuyNode(d);
  141.     if (pos == (*pplist))
  142.     {
  143.         newNode->next = *pplist;
  144.         *pplist = newNode;
  145.     }
  146.     else
  147.     {
  148.         pNode cur = *pplist;
  149.         while (cur&&cur->next != pos)
  150.         {
  151.             cur = cur->next;
  152.         }
  153.         if (cur)
  154.         {
  155.             newNode->next = pos;
  156.             cur->next = newNode;
  157.         }
  158.     }
  159. }
  161. void Erase(pList* pplist, pNode pos)//指定位置删除
  162. {
  163.     assert(pplist);
  164.     assert(pos);
  165.     if ((*pplist) == NULL)
  166.     {
  167.         return;
  168.     }
  169.     if ((*pplist) == pos)
  170.     {
  171.         *pplist = pos->next;
  172.         free(pos);
  173.         pos = NULL;
  174.     }
  175.     else
  176.     {
  177.         pNode cur = *pplist;
  178.         while (cur&&cur->next != pos)
  179.         {
  180.             cur = cur->next;
  181.         }
  182.         if (cur)
  183.         {
  184.             cur->next = pos->next;
  185.             free(pos);
  186.             pos = NULL;
  187.         }
  188.     }
  189. }
  191. void Remove(pList* pplist, DataType d)
  192. {
  193.     assert(pplist);
  194.     pNode cur = *pplist;
  195.     if ((*pplist) == NULL)
  196.     {
  197.         return;
  198.     }
  199.     if ((*pplist)->data == d)
  200.     {
  201.         *pplist = cur->next;
  202.         free(cur);
  203.         cur = NULL;
  204.     }
  205.     else
  206.     {
  207.         pNode del = cur;
  208.         while (cur&&del->data != d)
  209.         {
  210.             cur = cur->next;
  211.             del = cur->next;
  212.         }
  213.         if (cur)
  214.         {
  215.             cur->next = del->next;
  216.             free(del);
  217.             del = NULL;
  218.         }
  219.     }
  220. }
  222. //void ReMoveP(pList* pplist, DataType d) 
  223. //{
  224. //     pNode pCur = NULL;
  225. //     pNode pre = NULL;
  226. //     assert(pplist);
  227. //     if (NULL == (*pplist))
  228. //     {
  229. //         return;
  230. //     }
  231. //     pCur = (*pplist);
  232. //
  233. //     while (pCur)
  234. //     {
  235. //         pNode pDel = NULL;
  236. //         if (pCur->data == d)
  237. //         {
  238. //             if ((*pplist)->data == d)
  239. //             {
  240. //                 pCur = *pplist;
  241. //                 *pplist = (pCur)->next;
  242. //                 free(pCur);
  243. //                 pCur = *pplist;
  244. //             }
  245. //             else
  246. //             {
  247. //                 pre->next = pCur->next;
  248. //                 free(pCur);
  249. //                 pCur=pre;
  250. //
  251. //             }
  252. //         }
  253. //         else
  254. //         {
  255. //             pre = pCur;
  256. //             pCur = pCur->next;
  257. //         }
  258. //     }
  259. //}
  261. void RemoveAll(pList* pplist, DataType d)
  262. {
  263.     assert(pplist);
  264.     pNode cur = *pplist;
  265.     if ((*pplist) == NULL)
  266.     {
  267.         return;
  268.     }
  269.     pNode pre = *pplist;
  270.     while (cur)
  271.     {
  272.         if ((*pplist)->data == d)
  273.         {
  274.             cur = *pplist;
  275.             *pplist = (cur)->next;
  276.             free(cur);
  277.             cur = *pplist;
  278.         }
  279.         else if (cur->data == d)
  280.         {
  281.             pre->next = cur->next;    
  282.             free(cur);
  283.             cur = pre->next;
  284.         }
  285.         pre = cur;
  286.         cur = cur->next;
  287.     }
  288. }
  290. void PrintLinkList(pList plist)
  291. {
  292.     pNode cur = plist;
  293.     while (cur)
  294.     {
  295.         printf("%d->", cur->data);
  296.         cur = cur->next;
  297.     }
  298.     printf("NULL\n");
  299. }
  301. int GetListLength(pList plist)
  302. {
  303.     int count = 0;
  304.     pNode cur = plist;
  305.     while (cur)
  306.     {
  307.         count++;
  308.         cur = cur->next;
  309.     }
  310.     return count;
  311. }

  1. 从尾到头打印单链表

    • 递归调用

      void PrintTailToHead1(pList plist)//递归逆序打印单项链表
      {
      if (plist == NULL)
      return;
      PrintTailToHead1(plist->next);
      printf(“%d “, plist->data);
      }

    • 非递归，时间复杂度O(n^2)。

      void PrintTailToHead2(pList plist)//非递归逆序打印单项链表
      {
      pNode tail = NULL;
      pNode cur = plist;
      if (plist == NULL)

      1.   return;

      while (plist != tail)
      {

      1.   while (cur->next != tail)
      2.   {
      3.       cur = cur->next;
      4.   }
      5.   printf("%d ", cur->data);
      6.   tail = cur;
      7.   cur = plist;

      }
      }

  2. 删除一个无头单链表的非尾节点

70

  1. void EraseNotTailNode(pNode pos)
  2. {
  3.     assert(pos);
  4.     assert(pos->next);
  5.     pNode del = NULL;
  6.     del = pos->next;
  7.     pos->data = pos->next->data;
  8.     pos->next = del->next;
  9.     free(del);
  10.     del = NULL;
  11. }

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

    void InsertNode(pList* pplist, pNode pos, DataType d)//在无头单链表的一个节点之前插入一个节点
    {

    1.  assert(pplist);
    2.  assert(pos);
    3.  assert(*pplist);
    4.  pNode newNode = BuyNode(pos->data);
    5.  newNode->next = pos->next;
    6.  pos->next = newNode;
    7.  pos->data = d;

    }

  1. 单链表实现约瑟夫环

方法一：

70 2

  1. int pLinkNodeJosephCycle(pList * pplist, int num)
  2. {
  3.     pList tmp = NULL;
  4.     pList p = NULL;
  5.     p = (*pplist);
  6.     tmp = (*pplist);
  7.     while (tmp->next)
  8.     {
  9.         tmp = tmp->next;
  10.     }
  11.     tmp->next = (*pplist);
  12.     while ((*pplist) != (*pplist)->next)
  13.     {
  14.         for (int i = 1; i < num - 1; i++)
  15.         {
  16.             (*pplist) = (*pplist)->next;
  17.         }
  18.         p = (*pplist)->next;
  19.         (*pplist)->next = p->next;
  20.         free(p);
  21.         p = NULL;
  22.         (*pplist) = (*pplist)->next;
  23.     }
  24.     return (*pplist)->data;
  25. }

方法二：

70 3

  1. void JosephCycle(pList * pplist, int num)
  2. {
  3.     pList p = NULL;
  4.     p = (*pplist);
  5.     while (p!=p->next)
  6.     {
  7.         pNode del = NULL;
  8.         int count = num;
  9.         while(--count)
  10.         {
  11.             p=p->next;
  12.         }
  13.         printf("删除:%d\n",p->data);
  14.         del=p->next;
  15.         p->data = del->data;
  16.         p->next = del->next;
  17.         free(del);
  18.         del = NULL;
  19.     }
  20. }
  1. 逆置/反转单链表

70 4

  1. void ReverseList(pList* pplist)
  2. {
  3.     pList q = (*pplist);
  4.     pList p = q->next;
  5.     while (p)  //当p指向NULL时，表明倒置完成，退出循环
  6.     {
  7.         q->next = p->next;
  8.         p->next = (*pplist);
  9.         (*pplist) = p;
  10.         p = q->next;
  11.     }
  12. }

  1. 单链表排序（冒泡排序）

    void BubbleSort(pList * pplist)
    {

    1.  assert(pplist);
    2.  assert(*pplist);
    3.  pList q = NULL;
    4.  pList p = NULL;
    5.  for (int i = 0; i < GetListLength(*pplist); i++)
    6.  {
    7.      pList q = (*pplist);
    8.      pList p = q->next;
    9.      for (int j = 0; j < GetListLength(*pplist) - i - 1; j++)
    10.      {
    11.          while (p)
    12.          {
    13.              if (q->data < p->data)
    14.              {
    15.                  DataType tmp = q->data;
    16.                  q->data = p->data;
    17.                  p->data = tmp;
    18.              }
    19.              p = p->next;
    20.              q = q->next;
    21.          }
    22.      }
    23.  }

    }

  2. 合并两个有序链表,合并后依然有序
    //递归

    pNode Merge_R(pList plist1, pList plist2)//递归合并两个有序链表
    {

    1.  pNode  cur1 = plist1;
    2.  pNode  cur2 = plist2;
    3.  pNode  newlist = NULL;
    4.  if (cur1 == cur2)
    5.      return NULL;
    6.  if (cur1 == NULL)
    7.      return cur2;
    8.  if (cur2 == NULL)
    9.      return cur1;
    10.  if (cur1->data < cur2->data)
    11.  {
    12.      newlist = cur1;
    13.      newlist->next = Merge_R(cur1->next,cur2);
    14.  }
    15.  else
    16.  {
    17.      newlist = cur2;
    18.      newlist->next = Merge_R(cur1,cur2->next);
    19.  }
    20.  return newlist;

    }

    pNode Merge(pList plist1, pList plist2)//非递归合并两个有序链表
    {

    1.  pNode  cur1 = plist1;
    2.  pNode  cur2 = plist2;
    3.  pNode  head = NULL;
    4.  pNode  tail = NULL;
    5.  if (cur1 == NULL&&cur2 == NULL)//两条都为空不合并
    6.      return NULL;
    7.  if (cur1 == cur2)
    8.      return cur1;
    9.  if (cur1 == NULL)
    10.      return cur2;
    11.  if (cur2 == NULL)
    12.      return cur1;
    13.  if (cur1->data > cur2->data)
    14.  {
    15.      head = cur1;
    16.      cur1 = cur1->next;
    17.  }
    18.  else
    19.  {
    20.      head = cur2;
    21.      cur2 = cur2->next;
    22.  }
    23.  head->next = NULL;
    24.  tail = head;
    25.  while (cur1 != NULL&&cur2 != NULL)
    26.  {
    27.      if (cur1->data > cur2->data)
    28.      {
    29.          tail->next = cur1;
    30.          cur1 = cur1->next;
    31.      }
    32.      else
    33.      {
    34.          tail->next = cur2;
    35.          cur2 = cur2->next;
    36.      }
    37.      tail->next->next = NULL;
    38.      tail = tail->next;
    39.  }
    40.  if (cur1 == NULL)
    41.  {
    42.      tail->next = cur2;
    43.  }
    44.  else
    45.      tail->next = cur1;
    46.  return head;

    }

  3. 查找单链表的中间节点，要求只能遍历一次链表

70 5

  1. pNode FindMidNode(pList plist)//找中间节点
  2. {
  3.     pList fast = NULL;
  4.     pList slow = NULL;
  5.     if (NULL == plist)
  6.     {
  7.         return NULL;
  8.     }
  9.     else
  10.     {
  11.         //快慢指针
  12.         slow = plist;
  13.         fast = plist;
  14.         while ((NULL != fast) && (NULL != fast->next))
  15.         {
  16.             slow = slow->next;
  17.             fast = fast->next->next;
  18.         }
  19.         return slow;
  20.     }
  21. }

  1. 查找单链表的倒数第k个节点，要求只能遍历一次链表

    pNode FindLastKNode(pList plist, int k)
    {

    1. if ((NULL == plist) || (k <= 0))
    2. {
    3.     return NULL;
    4. }
    5. else
    6. {
    7.     pNode fast = plist;
    8.     pNode slow = plist;
    9.     //利用快慢指针，让快指针先走K-1步，然后两指针同时走，直到快指针指向的下一个结点为空为止
    10.     while (--k)
    11.     {
    12.         fast = fast->next;
    13.         if (NULL == fast)
    14.         {
    15.             return NULL;
    16.         }
    17.     }
    18.     while (NULL != fast->next)
    19.     {
    20.         fast = fast->next;
    21.         slow = slow->next;
    22.     }
    23.     return slow;
    24. }

    }

  2. 判断单链表是否带环？若带环，求环的长度？求环的入口点？并计算每个算法的时间复杂度&空间复杂度。

    pNode CheckCycle(pList pList)
    {

    1. if ((NULL == pList) || (NULL == pList->next))
    2. {
    3.     return NULL;
    4. }
    5. else
    6. {
    7.     pNode pFast = pList->next->next;
    8.     pNode pSlow = pList->next;
    9.     while (pFast != pSlow)
    10.     {
    11.         if (NULL == pFast)
    12.         {
    13.             return NULL;
    14.         }
    15.         else
    16.         {
    17.             pFast = pFast->next;
    18.             pSlow = pSlow->next;
    19.             if (NULL == pFast)
    20.             {
    21.                 return NULL;
    22.             }
    23.             else
    24.             {
    25.                 pFast = pFast->next;
    26.             }
    27.         }
    28.     }
    29.     return pFast;
    30. }

    }

    int GetCircleLength(pNode meet)
    {

    1. if (NULL == meet)
    2. {
    3.     return 0;
    4. }
    5. else
    6. {
    7.     int count = 1;
    8.     pNode pnode = meet;
    9.     while (meet != pnode->next)
    10.     {
    11.         pnode = pnode->next;
    12.         count++;
    13.     }
    14.     return count;
    15. }

    }

    pNode GetCycleEntryNode(pList plist, pNode meetNode)
    {

    1. pNode pnode = plist;
    2. if ((NULL == plist) || (NULL == meetNode))
    3. {
    4.     return NULL;
    5. }
    6. while (pnode != meetNode)
    7. {
    8.     pnode = pnode->next;
    9.     meetNode = meetNode->next;
    10. }
    11. return pnode;

    }

  3. 判断两个链表是否相交，若相交，求交点。（假设链表不带环）

    int CheckCross(pList p1, pList p2)
    {

    1. if((p1==NULL)||(p2==NULL))
    2.     return 0;
    3. pNode end1=p1;
    4. pNode end2=p2;
    5. while(end1->next!=NULL)
    6.     end1=end1->next;
    7. while(end2->next!=NULL)
    8.     end2=end2->next;
    9. if(end1==end2)
    10.     return 1;
    11. else return 0;

    }

  1. 判断两个链表是否相交，若相交，求交点。（假设链表可能带环）【升级版】

70 6

发表评论

表情：
评论列表 （有 0 条评论，271人围观）

还没有评论，来说两句吧...

相关阅读

    相关 【C++】单链表面试题

    链表是非常重要的内容，在面试时也是非常喜欢问的，下面是几个常见的面试题。 说明：这些题目中的链表都是指无头单链表。 代码的实现涉及到部分C++的语法。 typed

    我就是我我就是我/ 0 赞/ 282 阅读