写点什么

架构师训练营 - 第八周作业

用户头像
chenlovehx
关注
发布于: 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
用户头像

chenlovehx

关注

还未添加个人签名 2018.04.26 加入

还未添加个人简介

评论

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