本文共 2043 字,大约阅读时间需要 6 分钟。
AC 代码 总的来说,单链表分为两种 无环单链表,有环单链表,判断单链表相交则可转化为 俩无环单链表是否相交,俩有环单链表是否相交,而一条有环一条无环一定不可能相交!
class ChkIntersection { ListNode * findLoopNode(ListNode* head,int &len){//查找入环借点,若无环返回NULL;若无环即得到无环单链表长度 ListNode *quick=NULL,*slow=head->next; ++len; if(!slow) return NULL; quick = slow->next; ++len; while (true) { if(!quick||!slow) return NULL; if(quick == slow) break; slow = slow->next; quick = quick->next; ++len; if(!quick) return NULL; quick = quick->next; ++len; } quick = head; while (quick!=slow) { quick = quick->next; slow = slow->next; } return quick; } ListNode *walknums(ListNode *head,int nums){//让长的链表先走nums 步 while (nums--) { head = head->next; } return head; }public: bool chkInter(ListNode* head1, ListNode* head2, int adjust0, int adjust1) { if(!head1||!head2) return false; int len1 = 0,len2 = 0; ListNode * loop1 = findLoopNode(head1,len1), *loop2 = findLoopNode(head2,len2); if((loop1==NULL&&loop2)||(loop1&&loop2==NULL))//一个有环 ,一个无环 return false; else if(loop1==NULL&&loop2==NULL){//俩个都无环 if(len1>=len2) head1 = walknums(head1,len1-len2); else head2 = walknums(head2,len2-len1); while (head1&&head2) { if(head2==head1) return true; head1 = head1->next; head2 = head2->next; } return false; }else{//俩有环单链表相交 if(loop1==loop2) return true; else{ ListNode * p =loop1->next; while (p!=loop1) { if(p==loop2) return true; p = p->next; } return false; } } }};
转载地址:http://ghhji.baihongyu.com/