作业 1

判断2个链表是否合并

链表1 a->b->x->y->z

链表2 d->e->f->x->y->z



package demo;



import java.util.ArrayList;

import java.util.HashMap;

import java.util.List;

import java.util.Map;



public class TestLinked {



public static void main(String[] args) {

//生成2个链表

List<Node<String>> twoLinkedLists = getTwoLinkedLists();

Node<String> linkedList1 = twoLinkedLists.get(0);//链表1

Node<String> linkedList2 = twoLinkedLists.get(1);//链表2

//判断是否合并

Node<String> testMerged = testMerged(linkedList1,linkedList2);

if(testMerged!=null) {

System.out.println("有合并，合并在："+testMerged+" "+testMerged.getItem());

}else {

System.out.println("无合并");

}

}

/**

* 判断是否合并的方法

* @param linkedList1

* @param linkedList2

* @return Node<String> 合并的节点

* 时间复杂度O(n) 空间复杂度O(n)

*/

private static Node<String> testMerged(Node<String> linkedList1,Node<String> linkedList2){

Node<String> mergerdNode = null;

Object obj = new Object();

//使用缓存Map 存放其中一个链表

Map<Node<String>,Object> map = new HashMap<>();

//遍历链表1，将其中的每个节点放入缓存Map

while(linkedList1!=null) {

map.put(linkedList1, obj);

linkedList1 = linkedList1.getNext();

}

//遍历链表2，若其中某个节点存在于缓存Map中，即为合并

while(linkedList2!=null) {

if(map.containsKey(linkedList2)) {

mergerdNode = linkedList2;

break;

}

linkedList2 = linkedList2.getNext();

}

return mergerdNode;

}

private static List<Node<String>> getTwoLinkedLists(){

Node<String> a = new Node<>("a",null);

Node<String> b = new Node<>("b",null);

Node<String> x = new Node<>("x",null);

Node<String> y = new Node<>("y",null);

Node<String> z = new Node<>("z",null);

a.setNext(b);

b.setNext(x);

x.setNext(y);

y.setNext(z);

Node<String> d = new Node<>("d",null);

Node<String> e = new Node<>("e",null);

Node<String> f = new Node<>("f",null);

d.setNext(e);

e.setNext(f);

f.setNext(x);

// f.setNext(new Node<>("x",null));

List<Node<String>> list = new ArrayList<>();

list.add(a);

list.add(d);

return list;

}

private static class Node<String> {

String item;

Node<String> next;

public Node(String item, Node<String> next) {

super();

this.item = item;

this.next = next;

}

public Node<String> getNext() {

return next;

}

public void setNext(Node<String> next) {

this.next = next;

}

public String getItem() {

return item;

}

public void setItem(String item) {

this.item = item;

}

}

}