package com.demo.linklistmeet;
import java.util.TreeMap;
* @author niki-lauda
* @create 2020-07-26 10:28
*/
public class MeetTest {
public static void main(String[] args) {
Node node1 = new Node(1);
Node node2 = new Node(2);
Node node3 = new Node(3);
Node node4 = new Node(4);
Node node5 = new Node(5);
Node node6 = new Node(6);
Node node7 = new Node(7);
Node node8 = new Node(8);
Node node9 = new Node(9);
Node node10 = new Node(10);
node1.setNext(node2).setNext(node3).setNext(node4).setNext(node5).setNext(node3);
node6.setNext(node7).setNext(node8).setNext(node9).setNext(node10);
System.out.println(findMeetNode(node1, node1.getTotalSize(), node6, node6.getTotalSize()));
}
public static Node findMeetNode(Node head1, int list1Size, Node head2, int list2Size) {
double rate0 = list1Size / list2Size;
double rate1 = (Math.log(list1Size) / Math.log(2) - 1) / (Math.log(list2Size) / Math.log(2) - 1);
TreeMap<Integer, Node> dataMap = new TreeMap<>();
if(rate0 > rate1) {
while (head2 != null) {
if(dataMap.containsKey(head2.hashCode())) {
break;
}
dataMap.put(head2.hashCode(), head2);
head2 = head2.getNext();
}
while (head1 != null) {
Node nodeExist = dataMap.get(head1.hashCode());
if(nodeExist != null) {
return nodeExist;
}
head1 = head1.getNext();
}
} else {
while (head1 != null) {
if(dataMap.containsKey(head1.hashCode())) {
break;
}
dataMap.put(head1.hashCode(), head1);
head1 = head1.getNext();
}
while (head2 != null) {
Node nodeExist = dataMap.get(head2.hashCode());
if(nodeExist != null) {
return nodeExist;
}
head2 = head2.getNext();
}
}
return null;
}
}
class Node {
private Integer val;
private Node next;
private int totalSize = 1;
public Node(Integer val) {
this.val = val;
}
public Node getNext() {
return next;
}
public Node setNext(Node next) {
this.next = next;
totalSize++;
return next;
}
public int getTotalSize() {
return totalSize;
}
@Override
public String toString() {
final StringBuffer sb = new StringBuffer("Node{");
sb.append("val=").append(val);
sb.append('}');
return sb.toString();
}
}
评论