判断两个链表是否有公共节点

#include<iostream> using namespace std; struct ListNode { int value; struct ListNode * next; ListNode(int v = 0) :value(v), next(nullptr){} }; //判断是否有环，如果有环，返回环内节点；如果没有环，则返回nullptr ListNode * IsLoop(ListNode * head) { if (head == nullptr || head->next == nullptr) return nullptr; ListNode * slow = head; ListNode* fast = head->next; while (fast!=nullptr&&slow!=fast) { slow = slow->next; fast = fast->next; if (fast != nullptr) { fast = fast->next; } } return fast; } //计算环内长度 int LoopLenght(ListNode * head) { ListNode * stop = head; head = head->next; int count = 1; while (head!=stop) { count++; head = head->next; } return count; } //获得环的入口结点 ListNode* EntryLoop(ListNode * head,int length) { if (head==nullptr || length==0) { return nullptr; } ListNode * slow=head; ListNode * fast = head; for (int i = 0; i <length; i++) { fast = fast->next; } while (slow!=fast) { slow = slow->next; fast = fast->next; } return fast; } //计算带环，链表长度 int List_length(ListNode * head, ListNode * end,int loop) { int count = 0; while (head!=end) { count++; head = head->next; } return count+loop; } ListNode * ListMeet(ListNode* head1, ListNode * head2, int len1, int len2) { if (len1<len2) { swap(head1, head2); } int k = abs(len1 - len2); while (k--) { head1 = head1->next; } while (head1 != head2)//nullptr时相等 { head1 = head1->next; head2 = head2->next; } return head1; } bool TwoListMeet(ListNode * head1, ListNode* head2) { ListNode* isloop1= IsLoop(head1); ListNode* isloop2 = IsLoop(head2); //一个有环，一个无环，则必不存在交点 if ((isloop1==nullptr)^(isloop2==nullptr)) { return false; } //两个链表都没有环 if ((isloop1 == nullptr) &&(isloop2 == nullptr)) { int len1 = List_length(head1, nullptr, 0);//计算不带环链表长度 int len2 = List_length(head2, nullptr, 0); if(ListMeet(head1,head2,len1,len2)==nullptr)//可以保存meet节点 return false; else return true; } //两个链表都有环时 //环内长度 int looplenght1=LoopLenght(isloop1); int looplenght2 = LoopLenght(isloop2); //获得环的入口结点 ListNode* entry1 = EntryLoop(head1, looplenght1); ListNode* entry2 = EntryLoop(head2, looplenght2); //环外相遇 if (entry1==entry2) { //寻找相遇结点 int listlenght1 = List_length(head1, entry1, looplenght1);//计算带环链表长度 int listlenght2 = List_length(head2, entry2, looplenght2); ListNode* meet=ListMeet(head1, head2, listlenght1, listlenght2);//计算相遇节点 return true; } else { //判断是否在环内相遇 ListNode * temp = entry1; temp = temp->next; while (temp!=entry1&&temp!=entry2) { temp = temp->next; } if (temp == entry2) return true; else return false; } return false; } int main() { ListNode * node1 = new ListNode(1); ListNode * node2 = new ListNode(2); ListNode * node3 = new ListNode(3); ListNode * node4 = new ListNode(4); ListNode * node5 = new ListNode(5); ListNode * node6 = new ListNode(6); ListNode * node7 = new ListNode(7); node1->next = node2; node2->next = node3; node3->next = node4; node4->next = node1; node5->next = node6; node6->next = node4; node7->next = node6; bool flag=TwoListMeet(node5, node7); return 0; }

代码中如有不妥，欢迎指出！！

测试链表样列：

样列1：

样列2：