架构师训练营 - 第八周作业
发布于: 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 加入
还未添加个人简介
评论