1. 单链表小结腾讯面试题

题目：快速找到未知长度单链表的中间节点。
普通的方法很简单，首先遍历一遍单链表以确定单链表的长度L。然后再次从头节点出发循环L/2次找到单链表的中间节点。算法复杂度为：O(L+L/2)=O(3L/2)。

但是有一个很巧妙的方法：利用快慢指针！
利用快慢指针原理：设置两个指针search、mid都指向单链表的头节点。其中 search的移动速度是mid的2倍。当*search指向末尾节点的时候，mid正好就在中间了。这也是标尺的思想。我们来看下代码实现：

  1. bool GetMidNode(LinkList L, DataType* e)
  2. {
  3.     LinkList search, mid;
  4.     mid = search = L;
  6.     while (search->next != NULL)
  7.     {
  8.         //search移动的速度是 mid 的2倍
  9.         if (search->next->next != NULL)
  10.         {
  11.             search = search->next->next;
  12.             mid = mid->next;
  13.         }
  14.         else
  15.         {
  16.             search = search->next;
  17.         }
  18.     }
  19.     *e = mid->data;
  20.     return true;
  21. }

//写一个完整的程序，实现随机生成20个元素的链表（尾插法或头插法任意），用我们刚才学到的方法快速查找中间结点的值并显示。
GetMidNode2.c

2. 判断单链表中是否有环

eg - 图1
方法一：使用p、q两个指针，p总是向前走，但q每次都从头开始走，对于每个节点，看p走的步数是否和q一样。如图，当p从6走到3时，用了6步，此时若q从head出发，则只需两步就到3，因而步数不等，出现矛盾，存在环。
方法二：使用p、q两个指针，p每次向前走一步，q每次向前走两步，若在某个时候p == q，则存在环。

  1. // 比较步数的方法
  2. int HasLoop1(LinkList L)
  3. {
  4.     LinkList cur1 = L;  // 定义结点 cur1
  5.     int pos1 = 0;       // cur1 的步数
  7.     while (cur1)
  8.     {                       // cur1 结点存在
  9.         LinkList cur2 = L;  // 定义结点 cur2
  10.         int pos2 = 0;       // cur2 的步数
  11.         while (cur2)
  12.         {                           // cur2 结点不为空
  13.             if (cur2 == cur1)
  14.             {                       // 当cur1与cur2到达相同结点时
  15.                 if (pos1 == pos2)    // 走过的步数一样
  16.                     break;          // 说明没有环
  17.                 else                // 否则
  18.                 {
  19.                     printf("环的位置在第%d个结点处。\n\n", pos2);
  20.                     return 1;       // 有环并返回1
  21.                 }
  22.             }
  23.             cur2 = cur2->next;      // 如果没发现环，继续下一个结点
  24.             pos2++;                 // cur2 步数自增
  25.         }
  26.         cur1 = cur1->next;  // cur1继续向后一个结点
  27.         pos1++;             // cur1 步数自增
  28.     }
  29.     return 0;
  30. }
  32. // 利用快慢指针的方法
  33. int HasLoop2(LinkList L)
  34. {
  35.     int step1 = 1;
  36.     int step2 = 2;
  37.     LinkList p = L;
  38.     LinkList q = L;
  40.     while (p != NULL && q != NULL && q->next != NULL)
  41.     {
  42.         p = p->next;
  43.         if (q->next != NULL)
  44.             q = q->next->next;
  46.         printf("p:%d, q:%d \n", p->data, q->data);
  48.         if (p == q)
  49.             return 1;
  50.     }
  51.     return 0;
  52. }

3.双向循环链表实践

课堂演示题目：
要求实现用户输入一个数使得26个字母的排列发生变化，例如用户输入3，
输出结果：DEFGHIJKLMNOPQRSTUVWXYZABC
同时需要支持负数，例如用户输入-3，
输出结果：XYZABCDEFGHIJKLMNOPQRSTUVW

  1. #include<stdio.h>
  2. #include<stdlib.h>
  4. #define OK 1
  5. #define ERROR 0;
  7. typedef char ElemType;
  8. typedef int Status;
  9. typedef struct DualNode
  10. {
  11.     ElemType data;
  12.     struct DualNode* prior;
  13.     struct DualNode* next;
  14. }DualNode, * DuLinkList;
  16. Status InitList(DuLinkList* L)
  17. {
  18.     DualNode* p, * q;
  19.     int i;
  21.     *L = (DuLinkList)malloc(sizeof(DualNode));
  23.     if (!(*L))
  24.     {
  25.         return ERROR;
  26.     }
  28.     (*L)->next = (*L)->prior = NULL;
  29.     p = (*L);
  31.     for (i = 0; i < 26; i++)
  32.     {
  33.         q = (DualNode*)malloc(sizeof(DualNode));
  34.         if (!q)
  35.         {
  36.             return ERROR;
  37.         }
  39.         q->data = 'A' + i;
  40.         q->prior = p;
  41.         q->next = p->next;
  42.         p->next = q;
  43.         p = q;
  44.     }
  46.     p->next = (*L)->next;
  47.     (*L)->next->prior = p;
  49.     return OK;
  50. }
  52. void caser(DuLinkList* L, int i)
  53. {
  54.     if (i > 0)
  55.     {
  56.         do
  57.         {
  58.             (*L) = (*L)->next;
  59.         } while (--i);
  61.     }
  62.     if (i < 0)
  63.     {
  64.         i = i - 1;
  65.         (*L) = (*L)->next;
  67.         do
  68.         {
  69.             (*L) = (*L)->prior;
  70.         } while (++i);
  71.     }
  73. }
  75. int main()
  76. {
  77.     DuLinkList L;
  78.     int i, n;
  80.     InitList(&L);
  81.     printf("请输入一个整数:\n");
  82.     scanf_s("%d", &n);
  83.     printf("\n");
  85.     caser(&L, n);
  87.     for (i = 0; i < 26; i++)
  88.     {
  89.         L = L->next;
  90.         printf("%c", L->data);
  91.     }
  93.     printf("\n");
  95.     return 0;
  96. }

Vigenere（维吉尼亚）加密：当输入明文，自动生成随机密匙匹配明文中每个字母并移位加密。
eg - 图2
建议：当然你的随机密匙生成后不能丢掉，丢掉了就很难把明文还原来了，建议把随机密匙和密文加密存储在一起。