锐客网

  1. 首页 > it技术 > >

C|常见的单链表题目

c笔面试

一些常见的单链表题目，总结思路和实现代码。
1.单链表的反序
2.给单链表建环
3.检测单链表是否有环
4.给单链表解环
5.检测两条链表是否相交
6.不输入头节点，删除单链表的指定节点（只给定待删除节点指针）

1.单链表的反序

[cpp]view plain copy

  1. //逆转链表，并返回逆转后的头节点
  2. node* reverse(node *head)
  3. {
  4. if(head == NULL || head->next == NULL)
  5. {
  6. return head;
  7. }
  8. node *cur = head;
  9. node *pre = NULL;
  10. node *tmp;
  11. while(cur->next)
  12. {
  13. tmp = pre;
  14. pre = cur;
  15. cur = cur->next;
  16. pre->next = tmp; //操作pre的next逆转
  17. }
  18. cur->next = pre; //结束时，操作cur的next逆转
  19. return cur;
  20. }


2.给单链表建环


[cpp]view plain copy
  1. //给单链表建环，让尾指针，指向第num个节点，若没有，返回false
  2. bool bulid_looplink(node *head, int num)
  3. {
  4. node *cur = head;
  5. node *tail = NULL;
  6. int i = 0;
  7. if(num <= 0 || head == NULL)
  8. {
  9. return false;
  10. }
  11. for(i = 1; i < num; ++i)
  12. {
  13. if(cur == NULL)
  14. {
  15. return false;
  16. }
  17. cur = cur->next;
  18. }
  19. tail = cur;
  20. while(tail->next)
  21. {
  22. tail = tail->next;
  23. }
  24. tail->next = cur;
  25. return true;
  26. }


3.检测单链表是否有环

[cpp]view plain copy
  1. //检测单链表是否有环，快慢指针
  2. bool detect_looplink(node *head)
  3. {
  4. node *quick_node = head->next, *slow_node = head;
  5. if(head == NULL || head->next == NULL)
  6. {
  7. return false;
  8. }
  9. while(quick_node != slow_node)
  10. {
  11. if(quick_node == NULL || slow_node == NULL)
  12. break;
  13. quick_node = quick_node->next->next;
  14. slow_node = slow_node->next;
  15. }
  16. if(quick_node != NULL && slow_node != NULL)//非尾节点相遇
  17. return true;
  18. return false;
  19. }


4.给单链表解环
ps:为了增加节点位图的效率，本应使用hash或则红黑树，这里不造车了，直接用 set容器

[cpp]view plain copy
  1. //找到有环节点，并解环,找到并解环，返回true,无环，返回false
  2. //思路：先找到环节点：被2个节点指向的节点(一定有环的条件）ps:不考虑中间环，因为只有一个next节点，只可能是尾环
  3. bool unloop_link(node *head)
  4. {
  5. set node_bitmap; //node的地址位图
  6. unsigned int num = 0;
  7. node *cur = head, *pre = NULL;
  8. while(cur != NULL)
  9. {
  10. if(!node_bitmap.count(cur) )//该节点未被遍历过
  11. {
  12. node_bitmap.insert(cur);
  13. ++num;
  14. }
  15. else//指向已被遍历过的节点，此时pre节点为尾节点
  16. {
  17. pre->next = NULL;
  18. return true;
  19. }
  20. pre = cur;
  21. cur = cur->next;
  22. }
  23. return false;
  24. }


5.检测两条链表是否相交

[cpp]view plain copy
  1. //检测两条链表是否相交，是则返回第一个交点，否则返回NULL
  2. //思路：把2个链表各遍历一遍，记下长度length1和length2,若2者的尾节点指针相等，则相交。
  3. //之后再把长的链表从abs(len1-len2)的位置开始遍历，第一个相等的指针为目标节点
  4. node* detect_intersect_links(node *first_link, node *second_link)
  5. {
  6. int legnth1 = 1, length2 = 1, pos = 0;
  7. node *cur = NULL, *longer_link = first_link, *shorter_link = second_link;
  8. if(first_link == NULL || second_link == NULL)
  9. {
  10. return NULL;
  11. }
  12. while(first_link->next || second_link->next)//遍历2个链表
  13. {
  14. if(first_link->next)
  15. {
  16. first_link = first_link->next;
  17. ++legnth1;
  18. }
  19. if(second_link->next)
  20. {
  21. second_link = second_link->next;
  22. ++length2;
  23. }
  24. }
  25. if(first_link != second_link)//比较尾节点
  26. {
  27. return NULL;
  28. }
  29. pos = legnth1 - length2;
  30. if(legnth1 < length2)//保证 longer_link为长链表
  31. {
  32. pos = length2 - legnth1;
  33. cur = longer_link;
  34. longer_link = shorter_link;
  35. shorter_link = cur;
  36. }
  37. while(pos-- > 0)
  38. longer_link = longer_link->next;
  39. while(longer_link || shorter_link)
  40. {
  41. if(longer_link == shorter_link)//找到第一个交点
  42. {
  43. return longer_link;
  44. }
  45. longer_link = longer_link->next;
  46. shorter_link = shorter_link->next;
  47. }
  48. return NULL;
  49. }

6.不输入头节点，删除单链表的指定节点（只给定待删除节点指针）

[cpp]view plain copy
  1. //无头节点，随机给出单链表中一个非头节点，删除该节点，当传入空节点，或者尾节点时，返回false
  2. //思路：由于没有头节点，非循环单链表，无法获取目标节点的前节点，所以只能把它的next节点数据前移，并删除next节点
  3. //ps:当传入节点为尾节点，无法用此方法删除
  4. bool withouthead_delete_node(node *target_node)
  5. {
  6. node *cur = NULL;
  7. if(target_node == NULL || target_node->next == NULL)//空节点或者尾节点，失败
  8. {
  9. return false;
  10. }
  11. cur = target_node->next;
  12. target_node->name = cur->name;
  13. target_node->next = cur->next;
  14. delete cur;
  15. return true;
  16. }
【C|常见的单链表题目】

    推荐阅读


    上一篇：java|面试官提问:如何去掉list集合中重复的元素?

    下一篇：C|堆和栈