第八周作业：链表判断

关注

发布于: 2020 年 07 月 29 日

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
    请用（伪）代码描述算法，并给出时间复杂度。
﻿
﻿
算法思想：如果两个链表的末尾元素相同（指针相同，即为同一个元素，而非值相等），则合并。
若合并，则先遍历较长的链表，当两个链表长度一致时，同时遍历，找出第一个相同节点。
时间复杂度O(m+n)。
﻿
//判断两个单链表是否相交
bool  isIntersect(Node* Head1,Node* Head2)
{
 if(Head1==NULL||Head2==NULL)
 {
  return false;
 }
 Node* p1=Head1;
 Node* p2=Head2;
 //p1与p2记录两链表的尾指针
 while(p1->next!=NULL)
 {
  p1=p1->next;
 }
 while(p2->next!=NULL)
 {
  p2=p2->next;
 }
 if(p1==p2)
 {
  return true;
 }
 return false;
}
﻿