算法中常常会推断两条单链表是否相交，尽管算法简单，但也值得说一下。
代码中有详尽凝视。 Show you the code !
#undef UNICODE#include#include #include using namespace std;typedef struct _SINGLE_LIST { _SINGLE_LIST *Next; char Tag;} SINGLE_LIST, *PSINGLE_LIST;void main(){ PSINGLE_LIST Entry = NULL; char TagIndex = 'A'; PSINGLE_LIST Head1 = (PSINGLE_LIST)malloc(sizeof(SINGLE_LIST)); Entry = Head1; Entry->Tag = TagIndex++; Entry->Next = NULL; for (int i = 0; i < 6; i++) { Entry->Next = (PSINGLE_LIST)malloc(sizeof(SINGLE_LIST)); Entry->Next->Tag = TagIndex++; Entry->Next->Next = NULL; Entry = Entry->Next; } PSINGLE_LIST Head2 = (PSINGLE_LIST)malloc(sizeof(SINGLE_LIST)); Entry = Head2; Entry->Tag = TagIndex++; Entry->Next = NULL; for (int i = 0; i < 3; i++) { Entry->Next = (PSINGLE_LIST)malloc(sizeof(SINGLE_LIST)); Entry->Next->Tag = TagIndex++; Entry->Next->Next = NULL; Entry = Entry->Next; } // 构造一个交点 Entry->Next = Head1->Next->Next->Next; // 下图即为此时两个链表的连接情况 // +--------------------------------------------+ // | A -> B -> C -> D -> E -> F -> G | // | ^ | // | | | // | H -> I -> J -> K | // +--------------------------------------------+ // 方法一： // 循环遍历第一个链表中的每一项，查看是否在第二个链表中。由于两个单链表相交 // 遍历当中任一链表，至少一个或多个项在第二个链表中。在最坏的情况下，将运算 // m*n 次。 算法例如以下： BOOL IsIntersect = FALSE; PSINGLE_LIST IntersectEntry = NULL; Entry = Head1; while (Entry != NULL) { PSINGLE_LIST Entry2 = Head2; while (Entry2) { if (Entry == Entry2) { IsIntersect = TRUE; IntersectEntry = Entry; goto Result; } Entry2 = Entry2->Next; } Entry = Entry->Next; }Result: if (IsIntersect) { //cout << "Intersect: " << "True. " << "Tag - " << IntersectEntry->Tag << endl; cout << "Intersect: " << "True." << endl; } else { cout << "Intersect: " << "False" << endl; } // 方法二： // 观察上图不难发现假设两个单链表相交，那么最后一个项必定同样。所以假设站在仅仅推断单 // 链表是否相交的角度来看。算法事实上能够更简单。
两个链表各遍历一遍，找到最后一个项， // 检查是否同样。运算次数为 m+n。 算法例如以下： PSINGLE_LIST LastEntry1 = NULL; PSINGLE_LIST LastEntry2 = NULL; Entry = Head1; while (Entry != NULL) { Entry = Entry->Next; } LastEntry1 = Entry; Entry = Head2; while (Entry != NULL) { Entry = Entry->Next; } LastEntry2 = Entry; if (LastEntry1 == LastEntry2) { IsIntersect = TRUE; } if (IsIntersect) { //cout << "Intersect: " << "True. " << "Tag - " << IntersectEntry->Tag << endl; cout << "Intersect: " << "True." << endl; } else { cout << "Intersect: " << "False" << endl; } }
这就是编程之美。同样的问题採用不同的方法，效果全然不同。