写点什么

架构训练营第八周作业

用户头像
张锐
关注
发布于: 2020 年 07 月 28 日

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

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

public class LinkedListMerge {
public static void main(String args[]) {
Node head1 = genLinkedList('a', 'b', 'f', 'x', 'a', 'z');
Node head2 = genLinkedList('d', 'e', 'f', 'x', 'y', 'z');
Node mergePoint = findMerge(head1, head2);
System.out.println(mergePoint != null ? mergePoint.getC() : "Can't merge");
}
private static Node genLinkedList(Character ... chars) {
Node head = new Node();
Node p = head;
for (Character c : chars) {
Node n = new Node();
n.setC(c);
p.setNext(n);
p = p.next;
}
return head.next;
}
private static Node findMerge(Node head1, Node head2) {
if (head1 == null || head2 == null)
return null;
int len1 = getLength(head1);
int len2 = getLength(head2);
int base = Math.min(len1, len2);
Node rebase1 = rebase(head1, len1 - base);
Node rebase2 = rebase(head2, len2 - base);
boolean isContinue = false;
boolean isFirst = false;
Node result = null;
while(rebase1 != null && rebase2 != null) {
if (!rebase1.getC().equals(rebase2.getC())) {
isContinue = false;
isFirst = false;
} else {
if (!isFirst) {
isFirst = true;
result = rebase1;
}
isContinue = true;
}
rebase1 = rebase1.next;
rebase2 = rebase2.next;
}
return isContinue ? result : null;
}
/**
* 把head往后移动offset位置
*/
private static Node rebase(Node head, int offset) {
for (int i = 0; i < offset; i++) {
head = head.next;
}
return head;
}
private static int getLength(Node head) {
int i = 0;
while(head != null) {
i++;
head = head.next;
}
return i;
}
static class Node {
private char c;
private Node next;
public Character getC() {
return c;
}
public void setC(Character c) {
this.c = c;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
}

整体思路是:将两个链表从尾部对齐,然后从较短链表的头部位置开始搜索,如果能够找到到尾部的公共连续子串,就返回结果。

时间复杂度分析:getLength函数O(n),rebase函数O(n),在findMerge中找剩余链表,也是顺序往后查找,所以时间复杂度也是O(n)。综上,算法整体时间复杂度O(n)。运行结果:

('a', 'b', 'f', 'x', 'a', 'z');
('d', 'e', 'f', 'x', 'y', 'z')
结果:z



用户头像

张锐

关注

还未添加个人签名 2018.08.07 加入

还未添加个人简介

评论 (1 条评论)

发布
用户头像
作业请添加“极客大学架构师训练营”标签,便于分类
2020 年 07 月 29 日 17:50
回复
没有更多了
架构训练营第八周作业