周练习 8
发布于: 2020 年 11 月 15 日
有两个单向链表(链表长度分别为 m,n),这两个单向链表有可能在某个元素合并,也 可能不合并,如下图所示的这样。现在给定两个链表的头指针,在不修改链表的情况下, 如何快速地判断这两个链表是否合并?如果合并,找到合并的元素,也就是图中的 x 元 素。 请用代码(或伪代码)描述算法,并给出时间复杂度。
![](https://static001.geekbang.org/infoq/33/33153939255554e23125ab2788164fe7.png)
1 判断这两个链表是否合并,时间复杂度 O(N):
package com.example.week8;
import java.util.Iterator;
import java.util.LinkedList;
public class TestSet {
public static <T> boolean isMerge(LinkedList<T> list_m, LinkedList<T> list_n){
T last_m = getLast(list_m);
T last_n = getLast(list_n);
return last_m.equals(last_n);
}
public static <T> T getLast(LinkedList<T> list){
int m = list.size();
Iterator<T> iterator = list.iterator();
if (m == 1) {
return iterator.next();
}
T last = null;
for (int i = 0; i < m; i++) {
last = iterator.next();
}
return last;
}
public static void main(String[] args) {
LinkedList<String> list_m = new LinkedList<>();
list_m.add("a");
list_m.add("b");
list_m.add("x");
list_m.add("y");
list_m.add("z");
LinkedList<String> list_n = new LinkedList<>();
list_n.add("d");
list_n.add("e");
list_n.add("f");
list_n.add("x");
list_n.add("y");
list_n.add("z");
boolean merge = isMerge(list_m, list_n);
System.out.println(merge);
}
}
复制代码
2 找到合并的元素:
package com.example.week8;
import java.util.Iterator;
import java.util.LinkedList;
public class TestSet2 {
public static <T> T findMergePoint(LinkedList<T> list_m, LinkedList<T> list_n){
int m = list_m.size();
int n = list_n.size();
int offset = m - n;
int move = Math.abs(offset);
Iterator<T> iterator_m = list_m.iterator();
Iterator<T> iterator_n = list_n.iterator();
if(offset > 0) {
for (int i = 0; i < move; i++) {
iterator_m.next();
}
} else if (offset < 0) {
for (int i = 0; i < move; i++) {
iterator_n.next();
}
}
T target = null;
while (iterator_m.hasNext()){
T current_m = iterator_m.next();
T current_n = iterator_n.next();
if (current_m == current_n){
target = current_m;
break;
}
}
return target;
}
public static void main(String[] args) {
LinkedList<String> list_m = new LinkedList<>();
list_m.add("a");
list_m.add("b");
list_m.add("x");
list_m.add("y");
list_m.add("z");
LinkedList<String> list_n = new LinkedList<>();
list_n.add("d");
list_n.add("e");
list_n.add("f");
list_n.add("x");
list_n.add("y");
list_n.add("z");
String mergePoint = findMergePoint(list_m, list_n);
System.out.println(mergePoint);
}
}
复制代码
划线
评论
复制
发布于: 2020 年 11 月 15 日阅读数: 30
![用户头像](http://static001.geekbang.org/account/avatar/00/16/64/33/141eda4b.jpg?x-oss-process=image/resize,w_200,h_200)
何毅曦
关注
还未添加个人签名 2019.03.20 加入
还未添加个人简介
评论