架构师训练营 - 第八周作业
发布于: 2020 年 11 月 15 日
有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,也可能不合并,如下图所示的这样。现在给定两个链表的头指针,在不修改链表的情况下,如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元素。
请用代码(或伪代码)描述算法,并给出时间复杂度。
代码实现:
public class LinkNode {
public LinkNode(char num, LinkNode next) {
this.num = num;
this.next = next;
}
private char num;
private LinkNode next;
public char getNum() {
return num;
}
public void setNum(char num) {
this.num = num;
}
public LinkNode getNext() {
return next;
}
public void setNext(LinkNode next) {
this.next = next;
}
}
复制代码
public class Demo {
public static void main(String[] args) {
LinkNode first = new LinkNode('a',
new LinkNode('b',
new LinkNode('x',
new LinkNode('y',
new LinkNode('z', null)))));
LinkNode second = new LinkNode('d',
new LinkNode('e',
new LinkNode('f',
new LinkNode('x',
new LinkNode('y',
new LinkNode('z', null))))));
LinkNode commonNode = findFistCommonNode2(first, second);
System.out.println("当前合并的节点为:" + commonNode.getNum());
}
// 时间复杂度:O(len1+len2)
private static LinkNode findFistCommonNode1(LinkNode first, LinkNode second) {
Stack<LinkNode> firstStack = new Stack<>();
Stack<LinkNode> secondStack = new Stack<>();
LinkNode node = first;
while (node != null) {
firstStack.push(node);
node = node.getNext();
}
node = second;
while (node != null) {
secondStack.push(node);
node = node.getNext();
}
while (!firstStack.isEmpty() && !secondStack.isEmpty()) {
LinkNode node1 = firstStack.pop();
LinkNode node2 = secondStack.pop();
if (node1.getNum() != node2.getNum()) {
return node1.getNext();
}
}
return null;
}
// 时间复杂度:O(len1+len2)
private static LinkNode findFistCommonNode2(LinkNode first, LinkNode second) {
int len1 = 0;
int len2 = 0;
LinkNode temp = first;
while (temp != null) {
len1++;
temp = temp.getNext();
}
temp = second;
while (temp != null) {
len2++;
temp = temp.getNext();
}
LinkNode longNode;
LinkNode shortNode;
int index;
if (len1 > len2) {
index = len1 - len2;
longNode = first;
shortNode = second;
} else {
index = len2 - len1;
longNode = second;
shortNode = first;
}
while (index-- != 0) {
longNode = longNode.getNext();
}
while (longNode != null && longNode.getNum() != shortNode.getNum()) {
longNode = longNode.getNext();
shortNode = shortNode.getNext();
}
return longNode;
}
}
复制代码
以上两个方法的时间复杂度都是 O(len1+len2)。
划线
评论
复制
发布于: 2020 年 11 月 15 日阅读数: 24
版权声明: 本文为 InfoQ 作者【chenlovehx】的原创文章。
原文链接:【http://xie.infoq.cn/article/25272844b36568e0e765f7387】。文章转载请联系作者。
chenlovehx
关注
还未添加个人签名 2018.04.26 加入
还未添加个人简介
评论