日本代购网站怎么做的/软文300字介绍商品

判断两链表是否相交，求交点（假设链表不带环）

判断两链表是否相交，求交点（假设链表可能带环）

RingEntry_Point()等函数见前篇.

SListNode* Intersect(SListNode *&L, SListNode *&M)//判断两链表是否相交，求交点（假设链表不带环）
{//思路：若不带环，只有相交/不想交两种情况// 与RingEntry_Point()函数方法相同：//     求两个链表长度之差K，再令一个指针从长链表开始先走K步，令另一个指针从短链表头开始，//     两链表一起走，相遇点就为入口点if (L != NULL&&M != NULL){SListNode *cur = L;SListNode *NewNode = M;int c1 = _LengthNode(cur);int c2 = _LengthNode(NewNode);int minus = _LengthNode(cur) - _LengthNode(NewNode);if (minus > 0){while (minus--){cur = cur->next;}}else{int tmp = -minus;while (tmp--){NewNode = NewNode->next;}}while (NewNode != cur&&NewNode != NULL&&cur != NULL){NewNode = NewNode->next;cur = cur->next;}if (NewNode == NULL || cur == NULL)return NULL;return cur;}return NULL;
}SListNode* IntersectRing(SListNode *&L, SListNode *&M)//判断两链表是否相交，求交点（假设链表可能带环）
{//思路：考虑全部情况：1、不带环 相交/不相交  2、带环 一条带环一条不带环/两条都带环（其中又分交点不在环上/交点在环上）////区分是哪一种情况，分别实现if (L != NULL&&M != NULL){if (!IsRing(L) && !IsRing(M))//不带环return Intersect(L, M);else if ((IsRing(L) && !IsRing(M)) || (!IsRing(L) && IsRing(M)))//一条带环一条不带环return NULL;else{//先求两链表的环入口点，若入口点一样，则为第5种情况否则是第4、6种情况SListNode *re1 = RingEntry(L);SListNode *re2 = RingEntry(M);if (re1 == re2)//第5种情况 化为不带环相交链表问题{SListNode* m1 = IsRing(L);SListNode*recover = m1->next;// 复原仿照RingEntry_Point()函数m1->next = NULL;SListNode*cur = Intersect(L, M);m1->next = recover;return cur;}else//第4、6种情况若其中一个环入口点在另一个环上，则为第6种情况，否则为第4种情况{SListNode *tmp = re1->next;while (tmp != re1&&tmp != re2)tmp = tmp->next;if (tmp == re1)//第4种情况return NULL;printf("两链表带环，并且有两个交点\n");//第6种情况SListNode *tmp1 = re1->next;re1->next = NULL;PrintNode(re1);re1->next = tmp1;return re2;}}}elsereturn NULL;
}

测试

void Test10()
{printf("//Test10() Intersect() \n");SListNode *LL = NULL;PushBack(LL, 1);PushBack(LL, 2);PushBack(LL, 3);PushBack(LL, 4);PushBack(LL, 5);PrintNode(LL);SListNode *MM = NULL;PushBack(MM, 1);PushBack(MM, 2);MM->next->next = LL->next->next->next;PrintNode(MM);SListNode *NN = NULL;PushBack(NN, 7);PushBack(NN, 8);PushBack(NN, 9);PushBack(NN, 0);PrintNode(NN);SListNode* c1 = Intersect(LL, MM);SListNode* c2 = Intersect(LL, NN);PrintNode(c1);PrintNode(c2);
}void Test11()
{printf("//Test11() IntersectRing() \n");SListNode *LL = NULL;PushBack(LL, 1);PushBack(LL, 2);PushBack(LL, 3);PushBack(LL, 4);PushBack(LL, 5);PrintNode(LL);SListNode *NN = NULL;PushBack(NN, 6); PushBack(NN, 7);PushBack(NN, 8);PushBack(NN, 9);PushBack(NN, 0);PrintNode(NN);SListNode* c1 = IntersectRing(LL, NN);//第1种PrintNode(c1);printf("\n");SListNode *MM = NULL;//第2种PushBack(MM, 0);PushBack(MM, 1);MM->next->next = LL->next;SListNode* c2 = IntersectRing(LL, MM);PrintNode(c2);printf("\n");Find(LL, 5)->next = Find(LL, 3);//第3种SListNode* c3 = IntersectRing(LL, NN);SListNode* c4 = IntersectRing(NN, LL);PrintNode(c3);PrintNode(c4);printf("\n");Find(NN, 0)->next = Find(NN, 8);//第4种SListNode* c5 = IntersectRing(NN, LL);PrintNode(c5);printf("\n");SListNode* c6 = IntersectRing(MM, LL);//第5种SListNode* c7 = IntersectRing(LL, MM);SListNode* tmp1 = c6->next;c6->next = NULL;PrintNode(c6);c6->next = tmp1;SListNode* tmp2 = c7->next;c7->next = NULL;PrintNode(c7);c7->next = tmp2;printf("\n");Find(NN, 0)->next = Find(LL, 4);//第6种SListNode* c9 = IntersectRing(NN, LL);SListNode* tmp3 = c9->next;c9->next = NULL;PrintNode(c9);c9->next = tmp3;SListNode* c10 = IntersectRing(LL, NN);SListNode* tmp4 = c10->next;c10->next = NULL;PrintNode(c10);c10->next = tmp4;printf("\n");Find(LL, 5)->next = Find(LL, 1);//第6种Find(NN, 0)->next = Find(LL, 4);SListNode* c11 = IntersectRing(NN, LL);SListNode* tmp5 = c11->next;c11->next = NULL;PrintNode(c11);c11->next = tmp5;SListNode* c12 = IntersectRing(LL, NN);SListNode* tmp6 = c12->next;c12->next = NULL;PrintNode(c12);c12->next = tmp6;printf("\n");}