前言:
深知自己对于这个知识点掌握的不是很好, 故好好思考, 并记录下思考后的成果.
图示链表带环相交问题:
既然已经分析清楚, 那么代码就很好实现了...
- Node* IsHaveCrossNode(Node* head1,Node* head2)
- {
- assert(head1);
- assert(head2);
- Node* meetNode1 = IsCircle(head1);
- Node* meetNode2 = IsCircle(head2);
- // 排除第 1 种情况
- if (meetNode1 == NULL || meetNode2 == NULL)
- {
- return NULL;
- }
- // 说明两个链表都带环
- // 根据相遇点排除第 2 种情况
- Node* cur1 = meetNode1->_next;
- while (cur1 != meetNode1 && cur1 != meetNode2)
- {
- cur1 = cur1->_next;
- }
- if (cur1 != meetNode2)
- {
- return NULL;
- }
- // 区分第 3 和第 4 种情况 (需要求出两个入口点)
- Node* entry1 = GetEntryNode(head1, meetNode1);
- Node* entry2 = GetEntryNode(head2, meetNode2);
- // 第 3 种情况 (转化为求两个链表的交点, 链表不带环时)
- if (entry1 == entry2)
- {
- entry1->_next = NULL;
- entry2->_next = NULL;
- Node* meet = IsMeet(head1, head2);
- return meet;
- }
- // 第 4 种情况 (有两个入口点, 返回一个即可)
- return entry1;
- }
- // 判断一个链表是否带环
- // 思路: 快慢指针, 返回相遇点
- Node* IsCircle(Node* head)
- {
- if (head == NULL)
- {
- return NULL;
- }
- Node* pFast = head;
- Node* pSlow = head;
- // 快指针一次走两步, 慢指针一次走一步
- while (pFast && pFast->_next)
- {
- pFast = pFast->_next->_next;
- pSlow = pSlow->_next;
- if (pFast == pSlow)
- {
- break;
- }
- }
- if (pFast && pFast->_next)
- {
- return pFast;
- }
- return NULL;
- }
- Node* GetEntryNode(Node* head, Node* meetNode)
- {
- assert(head && meetNode);
- Node* p1 = head;
- Node* p2 = meetNode;
- while (p1 != p2)
- {
- p1 = p1->_next;
- p2 = p2->_next;
- }
- return p1;
- }
- // 判断是否相交, 判断尾节点
- // 若相交, 则返回交点
- Node* IsMeet(Node* head1,Node* head2)
- {
- assert(head1 && head2);
- Node* cur1 = head1;
- int count1 = 0;
- Node* cur2 = head2;
- int count2 = 0;
- while (cur1->_next)
- {
- ++count1;
- cur1 = cur1->_next;
- }
- while (cur2->_next)
- {
- count2++;
- cur2 = cur2->_next;
- }
- if (cur1 != cur2)
- {
- return NULL;// 说明没有交点
- }
- int D_val = count2 - count1;
- if (D_val <0)
- {
- D_val = -D_val;
- }
- //
- cur1 = head1;
- cur2 = head2;
- if (count1 < count2)
- {
- // 让 head2 链表先走 D_val 长度
- while (cur2 && D_val--)
- {
- cur2 = cur2->_next;
- }
- while (cur2 && cur1 != cur2)
- {
- cur1 = cur1->_next;
- cur2 = cur2->_next;
- }
- if (cur1 == cur2)
- {
- return cur1;
- }
- }
- else
- {
- // 让 head1 链表先走 D_val 长度
- while (cur1 && D_val--)
- {
- cur1 = cur1->_next;
- }
- while (cur1 && cur1 != cur2)
- {
- cur1 = cur1->_next;
- cur2 = cur2->_next;
- }
- if (cur1 == cur2)
- {
- return cur1;
- }
- }
- return NULL;
- }
来源: http://www.bubuko.com/infodetail-3460075.html