week8-- 课后作业

关注

发布于: 2020 年 07 月 30 日

有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。
1.比较两个链表的长度 m ,n 找到较长的那个
2.让 longList 的头指针向后移动 abs(m-n) 个节点；这样两个链表就一样长了
3.比较两个链表的头指针，如果一样则返回该节点；不一样则头指针分别往后移动一位 直到链表遍历结束
若返回为 null, 则表示两链表未合并；反之，则为合并节点。时间复杂度是 O(m+n)，空间复杂度O(1)，没有分配额外的空间。
﻿
int getLinkListLen(LinkList ha) {
 return len;
}
﻿
LinkList  getConnect(LinkList ha,LinkList hb){
int m = getLinkListLen(LinkList ha)
int n = getLinkListLen(LinkList hb)
	LinkList hc,rear;
    if(m>n){
        hc = ha;
        rear = hb;
    }else{
        hc = hb;
        rear = ha;
    }
   
    for (int i=0;i<abs(m-n))
        hc = hc.next;
    while(hc){
       if(hc == rear){
        return hc;
      }
      hc = hc.next();
      rear = rear.next();
    }
    return null;
    
}
﻿