架构师训练营第八周作业

第一题：

判断链表合并

方法1：

将链表1、链表2的头结点放入set，指针后移，直至发现set中已存在该节点，即为合并的节点。

时间复杂度O（m+n）



import java.util.HashSet;

import java.util.Set;



class Node {

String value;

Node next;

public Node(String value) {

this.value = value;

}

public String getValue() {

return value;

}

public void setValue(String value) {

this.value = value;

}

public Node getNext() {

return next;

}

public void setNext(Node next) {

this.next = next;

}

@Override

public String toString() {

return "Node [value=" + value + ", next=" + next + "]";

}

}

public class ListCombine {

public static void main(String[] args) {

Node a = new Node("a");

Node b = new Node("b");

Node d = new Node("d");

Node e = new Node("e");

Node f = new Node("f");

Node x = new Node("x");

Node y = new Node("y");

Node z = new Node("z");

a.setNext(b);

b.setNext(x);

d.setNext(e);

e.setNext(f);

f.setNext(x);

x.setNext(y);

y.setNext(z);

Set<Node> s = new HashSet<Node>();

Node h1 = a;

Node h2 = d;

while(h1 != null || h2 != null) {

if(h1 != null) {

if(s.contains(h1)) {

System.out.println(h1);

break;

} else {

s.add(h1);

h1 = h1.getNext();

}

}

if(h2 != null) {

if(s.contains(h2)) {

System.out.println(h2);

break;

} else {

s.add(h2);

h2 = h2.getNext();

}

}

}

}

}