周练习 8
发布于: 2020 年 11 月 15 日
有两个单向链表（链表长度分别为 m，n），这两个单向链表有可能在某个元素合并，也 可能不合并，如下图所示的这样。现在给定两个链表的头指针，在不修改链表的情况下， 如何快速地判断这两个链表是否合并？如果合并，找到合并的元素，也就是图中的 x 元 素。 请用代码（或伪代码）描述算法，并给出时间复杂度。
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
何毅曦
关注
还未添加个人签名 2019.03.20 加入
还未添加个人简介
评论