架构师训练营第八周作业

 关注

发布于: 2020 年 07 月 29 日

说明：有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，如下图所示的这样，也可能不合并。现在给定两个链表的头指针，在不修改链表的情况下，如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元素。
请用（伪）代码描述算法，并给出时间复杂度和空间复杂度。
﻿
一、题解分析采用双指针，以下列顺序分别遍历链表1和链表2：
pointerA先遍历链表1，遍历到z后，遍历链表2；
pointerB先遍历链表2，遍历在z后，遍历链表1；
因为pointerA和pointerB走的总距离为m+n，且最后都会遍历x到z，因此，如果相交，会同时到达x，此时，pointerA等于pointerB，如果不想交，最终pointerA也会等于pointerB，值为null。
时间复杂度：O(m+n)，空间复杂度为：O(1）。
二、代码
public Map getIntersectionNode(ListNode headA, ListNode headB) {
  Map result = new HashMap();
  result.put("hasIntersection", false);
  result.put("intersectionNode", null);
  if (headA == null || headB == null) {
    return result;
  }
  ListNode pointerA = headA;
  ListNode pointerB = headB;
  while (pointerA != pointerB) {
    pointerA = pointerA == null ? headB : pointerA.next;
    pointerB = pointerB == null ? headA : pointerB.next;
  }
  result.put("hasIntersection", pointerA != null);
  result.put("intersectionNode", pointerA);
  return result;
}
﻿

发布于: 2020 年 07 月 29 日阅读数: 35

养乐多

 关注

还未添加个人签名 2019.11.12 加入

还未添加个人简介

发布

暂无评论