描述：
有N个单向链表，每个链表中的元素都已经按照从小到大的顺序排序。需要找出N个链表中所有的公共元素
例如，给定一下三个链表时，输出2，2.
1-2-2-2-3-9
2-2-9
1-2-2-100
思路1：
建立一个map<int,int> mapCache; key值表示数值，val表示改值出现的次数。 遍历N个链表，并将所有出现的数值存入map。最后，判断一下如果某个key对应的count等于链表个数，则该key值是公共元素。
但是，改种思路未能处理单个链表中含有重复元素的情况，例如，以下两个链表：
2-2-3-6
4-9
思想：开辟辅助存储空间。例如：
思路2：
类似，将两个有序链表合并成一个有序链表。 同时遍历N个链表，遍历的同时对N个正在被遍历的节点进行比较，
如果发现某个链表已经结尾，则停止；
否则，判断当前正在被遍历的n个节点是否相等，相等则输出该值，同时所有链表同时前进一步，
否则，找出最小的节点对应的链表，并将这个链表前进一部。
show code:
以上给出的测试案例时通过的。
#pragma once #include <vector> #include <map> #include <iostream> using namespace std; class FindCommomNodes { public: FindCommomNodes(); ~FindCommomNodes(); struct Node { Node(int v = 0, Node* p=nullptr) : val(v), next(p) {} int val; Node* next; }; void printCommanNodes(std::vector<Node*> lists, int N) { if (lists.empty()) return; if (N != lists.size()) return; std::vector<Node*> activeNodes; activeNodes.clear(); for (auto pNode : lists) { activeNodes.push_back(pNode); } int returnVal = 0; while (-1 != (returnVal = judgeNodes(activeNodes)) ) { //终止条件：有任何一个list被遍历完了 //每次让其中的一个list递进一步，当所有的activeNode的值相等时，共同递进一步 if (-2 == returnVal) { std::cout<< activeNodes[0]->val << " "; for (auto& it : activeNodes) { it = it->next; } } else { activeNodes[returnVal] = activeNodes[returnVal]->next; } } } int judgeNodes(const std::vector<Node*>& activeNodes) { //return -1: 存在null //return -2: 所有active node的值相同，所有指针共同进一步 //return 0,1,2,....， 某个active node 自己进一步 //if (std::find(activeNodes.begin(), activeNodes.end(), nullptr) != activeNodes.end()) { // return -1; //} //vector没有find函数！ if (activeNodes.size() == 1) return -2; if (nullptr == activeNodes[0])//先判断一下，因为下面有activeNodes[0]->val return -1; bool allHaveSameVal = true; int firstVal = activeNodes[0]->val; int minValIdx = 0; int minVal = activeNodes[0]->val; for (int i = 0; i < activeNodes.size(); i++) { if (nullptr == activeNodes[i]) return -1; allHaveSameVal = allHaveSameVal& ((firstVal == activeNodes[i]->val)); if (minVal > activeNodes[i]->val){ minVal = activeNodes[i]->val; minValIdx = i; } } if (allHaveSameVal) { return -2; } else { return minValIdx; } } void Test() { int N = 3; std::vector<Node*> lists; lists.clear(); Node* p1 = new Node(1); p1->next = new Node(2); p1->next->next = new Node(2); p1->next->next->next = new Node(2); p1->next->next->next->next = new Node(3); p1->next->next->next->next->next = new Node(9); Node* p2 = new Node(2); p2->next = new Node(2); p2->next->next = new Node(9); Node* p3 = new Node(1); p3->next = new Node(2); p3->next->next = new Node(2); p3->next->next->next = new Node(100); lists.push_back(p1); lists.push_back(p2); lists.push_back(p3); printCommanNodes(lists, N); } };Test:
#include "FindCommomNodes.h" FindCommomNodes::FindCommomNodes() { } FindCommomNodes::~FindCommomNodes() { } int main() { FindCommomNodes obj; obj.Test(); return 0; }
