架构师训练营第八周作业

用户头像
0x12FD16B
关注
发布于: 2020 年 07 月 29 日

题目描述

有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。

请用(伪)代码描述算法,并给出时间复杂度和空间复杂度。



算法

  1. 首先遍历两个链表得到两个的长度, 将较长的链表标记为 long, 将较短的链表标记为 short

  2. 计算链表 long 和链表 short 的长度差 diff

  3. 使用两个指针 p1, p2 引用分别指向链表 long 和链表 short, 先让 p1 往前移动 diff 步

  4. 同时遍历两个链表直到找到相同节点或者到达链表尾部后退出

时空复杂度分析

时间复杂度: O(m + n), m 和 n 分别是链表 1 和链表 2 的长度;

空间复杂度: O(1)

代码实现

链表定义代码

public class Node {
public int val;
public Node next;
}

算法代码

public class Solution {
public Node intersectionPointOfTwoLinkedList(Node list1, Node list2) {
int length1 = length(list1), length2 = length(list2);
Node headLong = null, headShort = null;
if (length1 - length2 > 0) {
headLong = list1;
headShort = list2;
} else {
headLong = list2;
headShort = list1;
}
int diff = Math.abs(length1 - length2);
for (int i = 0; i < diff; i++) {
headLong = headLong.next;
}
while (headLong != null && headShort != null && headLong != headShort) {
headLong = headLong.next;
headShort = headShort.next;
}
return headLong;
}
private int length(Node list) {
int length = 0;
if (list != null) {
Node p = list;
while (p != null) {
length++;
p = p.next;
}
}
return length;
}
}



用户头像

0x12FD16B

关注

还未添加个人签名 2018.01.19 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营第八周作业