赞
踩
链表是编程中最常见的数据结构,当我们遍历链表时如果链表中存在闭环(如下图),会造成无限循环的情况。为了解决这个问题我们需要在遍历之前对链表做环检测。
我们设置两个指针如下图
然后快指针每次移动两个节点,慢指针每次移动一个节点,就像两个人在操场上跑,一个跑得快一个跑得慢,那么如果一直跑下去两人总会相遇。当两个指针相遇就代表链表存在闭环。此时的代码实现应该是这样的:
LinkedNode<T>* checkCycle() { LinkedNode<T> *fast, *slow; fast = this->head; slow = this->head; while (fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; if (fast == slow) { std::cout << "存在闭环,相遇点的值:" << fast->value << std::endl; return fast; } } return nullptr; }
这个时候我们已经可以确定链表是否有闭环,那么在进一步我们还可以找到闭环的入口。就是上图6的节点。
如下图所示,设链表中环外部分的长度为 L。指针进入环后,又走了 E的距离与 fast 相遇。此时,fast 指针已经走完了环的 n 圈,环长C。由于我们设定快指针是慢指针的2倍速度。因此有:R+E=n*C,演算过程如下:
由以上结果可知:如果此时第三个指针以和慢指针一样的速度从链表头开始出发,它和慢指针一定会在c点相遇,那么可以得知它们的第一次相遇点就是环入口。进一步完善上面的代码:
LinkedNode<T>* checkCycle() { LinkedNode<T> *fast, *slow; fast = this->head; slow = this->head; while (fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; if (fast == slow) { std::cout << "存在闭环,相遇点的值:" << fast->value << std::endl; fast = this->head; while (fast != slow) { fast = fast->next; slow = slow->next; } std::cout << "环入口值: " << fast->value << std::endl; return fast; } } return nullptr; }
/* List的单向链表实现 */ template <class T> class LinkedNode { public: T value; LinkedNode *next; LinkedNode(T value) { this->value = value; next = nullptr; } LinkedNode() { // value = default(); next = nullptr; } }; template <class T> class LinkedList { public: LinkedNode<T> *head; LinkedList(LinkedNode<T> *head) { this->head = head; } // 尾插法 bool add(LinkedNode<T> *node) { // 滑动指针 LinkedNode<T> *temp = this->head; while (temp->next != nullptr) { temp = temp->next; } temp->next = node; return true; } bool add(T t) { LinkedNode<T> *node = new LinkedNode<T>(t); this->add(node); return true; } int size() { if (checkLoop() != nullptr) { // 存在闭环则返回-1 return -1; } LinkedNode<T> *temp; temp = this->head; int size = 0; while (temp != nullptr) { size++; temp = temp->next; } return size; } LinkedNode<T>* checkLoop() { LinkedNode<T> *fast, *slow; fast = this->head; slow = this->head; while (fast->next != nullptr && fast->next->next != nullptr) { slow = slow->next; fast = fast->next->next; if (fast == slow) { std::cout << "存在闭环,相遇点的值:" << fast->value << std::endl; fast = this->head; while (fast != slow) { fast = fast->next; slow = slow->next; } std::cout << "环入口值: " << fast->value << std::endl; return fast; } } return nullptr; } // 遍历操作 void foreach( void(*fun)(T item, int index)) const { LinkedNode<T> *temp = this->head->next; int i = 0; while (temp != nullptr) { fun(temp->value, i++); temp = temp->next; } } // 映射操作 template<typename V> LinkedList<V> map(V(*fun)(T item, int index)) { LinkedList<V> newList(new LinkedNode<V>()); LinkedNode<T> *temp = this->head->next; int i = 0; while (temp != nullptr) { V res = fun(temp->value, i++); newList.add(res); temp = temp->next; } return newList; } };
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。