现在的位置: 首页 > 综合 > 正文

雅虎面试题─将两个双向循环链表中data值相同的结点删除

2019年01月04日 ⁄ 综合 ⁄ 共 3944字 ⁄ 字号 小 中 大 ⁄ 评论关闭

有双向循环链表结点定义为：

struct node
{ 
  int data;
  struct node *front,*next;
};

有两个双向循环链表A，B，知道其头指针为：pHeadA,pHeadB，请写一函数将两链表中data值相同的结点删除。

用两个向量A_vec、B_vec分别存储链表A、B的元素值，将A_vec、B_vec排序，用类似归并排序的方法把A_vec、B_vec中值相同的元素放到向量common_vec中。分别遍历链表A、B，用二分查找法查看每个节点元素是否在common_vec中。

[cpp] view
plaincopy

  1. // 链表结点  
  2. template <typename T>  
  3. class dc_list_node  
  4. {  
  5. public:  
  6.     dc_list_node(const T &item = T(), dc_list_node<T> *p_front = NULL, dc_list_node<T> *p_next = NULL):  
  7.         m_item(item), mp_front(p_front), mp_next(p_next)  
  8.     {}  
  9.       
  10.     T m_item;  
  11.     dc_list_node<T> *mp_front;  
  12.     dc_list_node<T> *mp_next;  
  13. private:  
  14.     dc_list_node(const dc_list_node<T> &);  
  15.     dc_list_node<T> &operator=(const dc_list_node<T> &);  
  16. };  


[cpp] view
plaincopy

  1. void dc_list_erase_node_with_equal_value(dc_list_node<int> *&p_headA, dc_list_node<int> *&p_headB)  
  2. {  
  3.     if (p_headA == NULL || p_headB == NULL)  
  4.         return;  
  5.     // A_vec存储链表A的元素值，B_vec存储链表B的元素值  
  6.     std::vector<int> A_vec, B_vec, common_vec;  
  7.     dc_list_node<int> *p_node;  
  8.     A_vec.push_back(p_headA->m_item);  
  9.     p_node = p_headA->mp_next;  
  10.     while (p_node != p_headA)  
  11.     {  
  12.         A_vec.push_back(p_node->m_item);  
  13.         p_node = p_node->mp_next;  
  14.     }  
  15.     B_vec.push_back(p_headB->m_item);  
  16.     p_node = p_headB->mp_next;  
  17.     while (p_node != p_headB)  
  18.     {  
  19.         B_vec.push_back(p_node->m_item);  
  20.         p_node = p_node->mp_next;  
  21.     }  
  22.     // 将A_vec和B_vec排序  
  23.     std::sort(A_vec.begin(), A_vec.end());  
  24.     std::sort(B_vec.begin(), B_vec.end());  
  25.     // 合并A_vec和B_vec相同的元素值到common_vec  
  26.     std::size_t i = 0, j = 0;  
  27.     while (i < A_vec.size() && j < B_vec.size())  
  28.     {  
  29.         if (A_vec[i] < B_vec[j])  
  30.             ++i;  
  31.         else if (A_vec[i] > B_vec[j])  
  32.             ++j;  
  33.         else  
  34.         {  
  35.             common_vec.push_back(A_vec[i]);  
  36.             ++i;  
  37.             ++j;  
  38.         }  
  39.     }  
  40.     // 分别遍历链表A和B，删除在元素值common_vec中的结点  
  41.     p_node = p_headA;  
  42.     for (i = 0; i < A_vec.size(); ++i)  
  43.     {  
  44.         if (std::binary_search(common_vec.begin(), common_vec.end(), p_node->m_item)) // 当前结点是值相同的结点  
  45.         {  
  46.             if (p_node == p_headA && p_node->mp_next == p_headA) // 链表中只有头结点一个结点  
  47.             {  
  48.                 delete p_headA;  
  49.                 p_headA = NULL;  
  50.                 break;  
  51.             }  
  52.             else if (p_node == p_headA) // 当前结点是头结点  
  53.             {  
  54.                 p_headA = p_node->mp_next;  
  55.                 p_headA->mp_front = p_node->mp_front;  
  56.                 p_node->mp_front->mp_next = p_headA;  
  57.                 p_node = p_headA;  
  58.             }  
  59.             else  
  60.             {  
  61.                 dc_list_node<int> *p_next = p_node->mp_next, *p_front = p_node->mp_front;  
  62.                 p_next->mp_front = p_front;  
  63.                 p_front->mp_next = p_next;  
  64.                 delete p_node;  
  65.                 p_node = p_next;  
  66.             }  
  67.         }  
  68.         else  
  69.             p_node = p_node->mp_next;  
  70.     }  
  71.     p_node = p_headB;  
  72.     for (i = 0; i < B_vec.size(); ++i)  
  73.     {  
  74.         if (std::binary_search(common_vec.begin(), common_vec.end(), p_node->m_item)) // 当前结点是值相同的结点  
  75.         {  
  76.             if (p_node == p_headB && p_node->mp_next == p_headB) // 链表中只有头结点一个结点  
  77.             {  
  78.                 delete p_headB;  
  79.                 p_headB = NULL;  
  80.                 break;  
  81.             }  
  82.             else if (p_node == p_headB) // 当前结点是头结点  
  83.             {  
  84.                 p_headB = p_node->mp_next;  
  85.                 p_headB->mp_front = p_node->mp_front;  
  86.                 p_node->mp_front->mp_next = p_headB;  
  87.                 p_node = p_headB;  
  88.             }  
  89.             else  
  90.             {  
  91.                 dc_list_node<int> *p_next = p_node->mp_next, *p_front = p_node->mp_front;  
  92.                 p_next->mp_front = p_front;  
  93.                 p_front->mp_next = p_next;  
  94.                 delete p_node;  
  95.                 p_node = p_next;  
  96.             }  
  97.         }  
  98.         else  
  99.             p_node = p_node->mp_next;  
  100.     }  
  101. }  

返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞