题解 | #牛牛的冒险旅程#
牛牛的冒险旅程
https://www.nowcoder.com/practice/79f7bf3d985c4b33af6d048ab53848d6
/** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param head ListNode类 * @return int整型 */ //辗转相除法 int gcd(int x, int y) { if(y == 0) { return x; } return gcd(y,x%y); } //分治法求vt.size()个数字的最小公约数,执行log2(vt.size())次 int divideGcd(vector<int> vt, int left, int right) { if(left > right) { return 1; } else if(left == right) { return vt[left]; } int mid = (left+right)/2; return gcd(divideGcd(vt,left,mid),divideGcd(vt,mid+1,right)); } int gcdInCycle(ListNode* head) { // write code here //排除空指针或只有一个指针的情况(单链表时不会成环) if(head == nullptr||head->next == nullptr) return -1; ListNode* curr = head; ListNode* pre = new ListNode(-1); pre->next = curr; //利用哈希表键唯一性确定是否存在环 map<int,int> mp; while(curr != nullptr) { mp[curr->val]++; if(mp[curr->val] > 1) { break; } curr = curr->next; pre = pre->next; } //若可以走到链表尾部,说明不存在环 if(curr == nullptr) return -1; //否则说明通过break跳出循环,此时curr刚好回到环的“初始”节点,pre指向环的“尾部”节点 //将环断开 pre->next = nullptr; vector<int> vt; //将“环”所有节点的值插入vector while(curr != nullptr) { vt.push_back(curr->val); curr = curr->next; } return divideGcd(vt, 0, vt.size()-1); } };