架构师训练营 - 命题作业 第 8 周

用户头像
水边
关注
发布于: 9 小时前
  • 有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,如下图所示的这样,也可能不合并。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。

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



解答:

需求分析:

  • 假设 m和n已知,且 m >= n

  • 如果2个链表在x结点合并,则2个链表从x结点开始到结束的结点完全一致。

  • 假设2个链表一定存在合并,n链接的第1个结点到x结点有P个结点,且x结点到结束结点有Q个结点

则我们可以知道: m >= n >= Q P + Q = n

那么算法遍历,应该从n链表的第一个结点开始,应该从m链表的第 (m - n) 个结点开始遍历,

然后每次都同时递进这2个链接,并对比所在结点是否相同。

由上述描述可知:

时间复杂度是 O(m),空间复杂度是O(1)。

注意:如果一开始,不知道m和n的大小关系,则需要先 各遍历一遍2个链表,以便得到m和n这2个长度值,时间复杂度变成 O(2m)



m和n未知时,代码如下

已提交到Github: https://github.com/youbl/study/tree/master/linkedlist-merge-find

单向链表类定义:

package cn.beinet;
public class LinkedList {
private String data;
private LinkedList nextNode;
public LinkedList(String data) {
this.data = data;
}
public String getData() {
return data;
}
public void setData(String data) {
this.data = data;
}
public LinkedList getNextNode() {
return nextNode;
}
public void setNextNode(LinkedList nextNode) {
this.nextNode = nextNode;
}
}



测试主调类:

package cn.beinet;
public class Main {
public static void main(String[] args) {
// 数据初始化
LinkedList listM = initListM();
LinkedList listN = initListN();
// 添加合并结点,注释这一句,可测试无合并场景
appendSameNode(listM, listN);
// 开始查找
LinkedList mergeNode = findMergeNode(listM, listN);
if (mergeNode == null)
System.out.println("不存在合并结点");
else
System.out.println("2个链表合并于结点: " + mergeNode.getData());
}
/**
* 查找2个单向链表的合并结点,无合并时,返回null
*
* @param listM 链表m
* @param listN 链表n
* @return
*/
private static LinkedList findMergeNode(LinkedList listM, LinkedList listN) {
int m = getLen(listM);
int n = getLen(listN);
// 交换,确保listM是较大的链表
if (m < n) {
LinkedList tmp = listM;
listM = listN;
listN = listM;
int tmpNum = m;
m = n;
n = tmpNum;
}
System.out.println("链表m长度 " + m + ", 链表n长度 " + n);
listM = jumpToSameNum(listM, m - n); // m链表先遍历,确保m链表剩下的结点数 跟n链表一致
for (int i = 0; i < n; i++) {
if (listM.equals(listN))
return listM;
listM = listM.getNextNode();
listN = listN.getNextNode();
}
return null;
}
private static int getLen(LinkedList list) {
int ret = 1;
while (list.getNextNode() != null) {
ret++;
list = list.getNextNode();
}
return ret;
}
// 大的链表,先遍历掉前面的结点,以便跟小链表同步
private static LinkedList jumpToSameNum(LinkedList list, int jumpNum) {
for (int i = 0; i < jumpNum; i++)
list = list.getNextNode();
return list;
}
private static LinkedList initListM() {
LinkedList head = new LinkedList("d");
LinkedList node1 = new LinkedList("e");
head.setNextNode(node1);
LinkedList node2 = new LinkedList("f");
node1.setNextNode(node2);
return head;
}
private static LinkedList initListN() {
LinkedList head = new LinkedList("a");
LinkedList node = new LinkedList("b");
head.setNextNode(node);
return head;
}
// 添加相同结点
private static void appendSameNode(LinkedList listM, LinkedList listN) {
while (listM.getNextNode() != null)
listM = listM.getNextNode();
while (listN.getNextNode() != null)
listN = listN.getNextNode();
LinkedList node1 = new LinkedList("x");
listM.setNextNode(node1);
listN.setNextNode(node1);
LinkedList node2 = new LinkedList("y");
node1.setNextNode(node2);
LinkedList node3 = new LinkedList("z");
node2.setNextNode(node3);
}
}



最终输出结果:

链表m长度 6, 链表n长度 5
2个链表合并于结点: x



发布于: 9 小时前 阅读数: 5
用户头像

水边

关注

还未添加个人签名 2019.04.14 加入

还未添加个人简介

评论

发布
暂无评论
架构师训练营 - 命题作业 第 8 周