51Testing软件测试论坛

 找回密码
 (注-册)加入51Testing

QQ登录

只需一步,快速开始

微信登录,快人一步

手机号码,快捷登录

查看: 2842|回复: 2
打印 上一主题 下一主题

[转贴] 四道有趣的单链表面试题

[复制链接]

该用户从未签到

跳转到指定楼层
1#
发表于 2017-7-18 11:55:25 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
四道有趣的单链表面试题(单链表反序、找出链表的中间元素、链表排序、判断一个单链表是否有环)
以下给出链表结点的数据结构:
  1. typedef struct _list_node  
  2. {  
  3.     double keyVal;  
  4.     _list_node *next;  
  5. }ListNode;
复制代码
Q1 单链表的反序
  1. ListNode* reverseList(ListNode* head)  
  2. {  
  3.     ListNode *p1, *p2 , *p3;  
  4.     //链表为空,或是单结点链表直接返回头结点  
  5.     if (head == NULL || head->next == NULL)  
  6.     {  
  7.         return head;  
  8.     }  
  9.     p1 = head;  
  10.     p2 = head->next;  
  11.     while (p2 != NULL)  
  12.     {  
  13.         p3 = p2->next;  
  14.         p2->next = p1;  
  15.         p1 = p2;  
  16.         p2 = p3;  
  17.     }  
  18.     head->next = NULL;  
  19.     head = p1;  
  20.     return head;  
  21. }
复制代码
Q2 找出链表的中间元素
思路分析:
    单链表的一个比较大的特点用一句广告语来说就是“不走回头路”,不能实现随机存取(random access)。如果我们想要找一个数组a的中间元素,直接a[len/2]就可以了,但是链表不行,因为只有a[len/2 - 1] 知道a[len/2]在哪儿,其他人不知道。因此,如果按照数组的做法依样画葫芦,要找到链表的中点,我们需要做两步(1)知道链表有多长(2)从头结点开始顺序遍历到链表长度的一半的位置。这就需要1.5n(n为链表的长度)的时间复杂度了。有没有更好的办法呢?有的。想法很简单:两个人赛跑,如果A的速度是B的两倍的话,当A到终点的时候,B应该刚到中点。这只需要遍历一遍链表就行了,还不用计算链表的长度。
下面的代码就体现了这个想法
  1. ListNode* find_midlist(ListNode* head)  
  2. {  
  3.     ListNode *p1, *p2;  
  4.     if (head == NULL || head->next == NULL)  
  5.     {  
  6.         return head;  
  7.     }  
  8.     p1 = p2 = head;  
  9.     while (1)  
  10.     {  
  11.         if (p2->next != NULL && p2->next->next != NULL)  
  12.         {  
  13.             p2 = p2->next->next;  
  14.             p1 = p1->next;  
  15.         }  
  16.         else  
  17.         {  
  18.             break;  
  19.         }  
  20.     }  
  21.     return p1;  
  22. }
复制代码
Q3  链表排序
思路分析:
   链表排序最好使用归并排序算法。堆排序、快速排序这些在数组排序时性能非常好的算法,在链表只能“顺序访问”的魔咒下无法施展能力;但是归并排序却如鱼得水,非但保持了它O(nlogn)的时间复杂度,而且它在数组排序中广受诟病的空间复杂度在链表排序中也从O(n)降到了O(1)。真是好得不得了啊,哈哈。以上程序是递推法的程序,另外值得一说的是看看那个时间复杂度,是不是有点眼熟?对!这就是分治法的时间复杂度,归并排序又是divide and conquer。
  1. double cmp(ListNode *p ,ListNode *q)  
  2. {  
  3.     return (p->keyVal - q->keyVal);  
  4. }  
  5.   
  6. ListNode* mergeSortList(ListNode *head)  
  7. {  
  8.     ListNode *p, *q, *tail, *e;  
  9.     int nstep = 1;  
  10.     int nmerges = 0;  
  11.     int i;  
  12.     int psize, qsize;  
  13.     if (head == NULL || head->next == NULL)  
  14.     {  
  15.         return head;  
  16.     }  
  17.     while (1)  
  18.     {  
  19.         p = head;  
  20.         tail = NULL;  
  21.         nmerges = 0;  
  22.         while (p)  
  23.         {  
  24.             nmerges++;  q = p;  psize = 0;  
  25.             for (i = 0; i < nstep; i++){  
  26.                 psize++;  
  27.                 q = q->next;  
  28.                 if (q == NULL)break;  
  29.             }  
  30.             qsize = nstep;  
  31.             while (psize >0 || (qsize >0 && q))  
  32.             {  
  33.                 if (psize == 0 )  
  34.                 {  
  35.                     e = q;  
  36.                     q = q->next;  
  37.                     qsize--;  
  38.                 }  
  39.                 else if (q == NULL || qsize == 0)  
  40.                 {  
  41.                     e = p;  
  42.                     p = p->next;  
  43.                     psize--;  
  44.                 }  
  45.                 else if (cmp(p,q) <= 0)  
  46.                 {  
  47.                     e = p;  
  48.                     p = p->next;  
  49.                     psize--;  
  50.                 }  
  51.                 else  
  52.                 {  
  53.                     e = q;  
  54.                     q = q->next;  
  55.                     qsize--;  
  56.                 }  
  57.                 if (tail != NULL)  
  58.                 {  
  59.                     tail->next = e;  
  60.                 }  
  61.                 else  
  62.                 {  
  63.                     head = e;  
  64.                 }  
  65.                 tail = e;  
  66.             }  
  67.             p = q;  
  68.         }  
  69.         tail->next = NULL;  
  70.         if (nmerges <= 1)  
  71.         {  
  72.             return head;  
  73.         }  
  74.         else  
  75.         {  
  76.             nstep <<= 1;  
  77.         }  
  78.     }  
  79. }
复制代码
Q4  判断一个单链表是否有环
  1. int is_looplist (ListNode *head)  
  2. {  
  3.     ListNode *p1, *p2;  
  4.     p1 = p2 = head;  
  5.     if (head == NULL || head->next == NULL)  
  6.     {  
  7.         return 0;  
  8.     }  
  9.     while (p2->next != NULL && p2->next->next != NULL)  
  10.     {  
  11.         p1 = p1->next;  
  12.         p2 = p2->next->next;  
  13.         if (p1 == p2)  
  14.         {  
  15.             return 1;  
  16.         }  
  17.     }  
  18.     return 0;  
  19. }
复制代码
思路分析:
   这道题是《C专家编程》中的题了。其实算法也有很多,比如说:我觉得进行对访问过的结点进行标记这个想法也不错,而且在树遍历等场合我们也经常使用。但是在不允许做标记的场合就无法使用了。在种种限制的条件下,就有了上面的这种算法,其实思想很简单:就像两个人在操场上跑步一样,只要有个人的速度比另一个人的速度快一点,他们肯定会有相遇的时候的。不过带环链表与操场又不一样,带环链表的状态是离散的,所以选择走得快的要比走得慢的快多少很重要。比如说这里,如果一个指针一次走三步,一个指针一次走一步的话,很有可能它们虽然在一个环中但是永远遇不到,这要取决于环的大小以及两个指针初始位置相差多少了。呵呵。你能看出两个指针的速度应该满足什么关系才能在有环的情况下相遇吗?如果你知道,不妨跟我讨论一下,呵呵。

分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
收藏收藏
回复

使用道具 举报

  • TA的每日心情
    奋斗
    6 小时前
  • 签到天数: 2819 天

    连续签到: 1 天

    [LV.Master]测试大本营

    2#
    发表于 2017-7-18 13:12:00 | 只看该作者
    很久没有做算法题了。。。
    回复 支持 反对

    使用道具 举报

  • TA的每日心情
    无聊
    2024-7-12 13:16
  • 签到天数: 1 天

    连续签到: 1 天

    [LV.1]测试小兵

    3#
    发表于 2017-7-18 15:11:56 | 只看该作者
    楼主厉害啊
    回复 支持 反对

    使用道具 举报

    本版积分规则

    关闭

    站长推荐上一条 /1 下一条

    小黑屋|手机版|Archiver|51Testing软件测试网 ( 沪ICP备05003035号 关于我们

    GMT+8, 2024-11-25 13:38 , Processed in 0.063731 second(s), 22 queries .

    Powered by Discuz! X3.2

    © 2001-2024 Comsenz Inc.

    快速回复 返回顶部 返回列表