写点什么

第八周作业

用户头像
Geek_ac4080
关注
发布于: 2020 年 11 月 15 日

链表节点对象

public class Node {
private int data;
private Node next;
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Node(int data) {
this.data = data;
}
}

两个链表共同构成了一个Y型。因此,只要分别遍历这两个链表,找到尾端节点,判断尾端节点是否相同即可确认是否相交

只需要先得到两个链表的差,用两个指针分别指向这两个链表P1,P2假定P1与P2相差为N,那么将P1移动N个节点后,才能使得P1与P2同在一个起跑线,接着同时出发,第一个相等的节点即为交点



public static Node getFirstJoinNode(Node h1,Node h2) {
int length1 = 0;
int length2 = 0;
Node node1 = h1;
Node node2 = h2;
while(null != node1.getNext()) {
length1 ++;
node1 = node1.getNext();
}
while(null != node2.getNext()) {
length1 ++;
node2 = node2.getNext();
}
if(length1 > length2){
int count = length2 - length1;
while(count > 0){
h2 = h2.getNext();
count-- ;
}
}else{
int count = length1 - length2;
while(count > 0){
h1 = h1.getNext();
count-- ;
}
}
while (h1 != h2) {
h1 = h1.getNext();
h2 = h2.getNext();
}
return h1 == h2 ? h1 : null;
}



用户头像

Geek_ac4080

关注

还未添加个人签名 2019.05.09 加入

还未添加个人简介

评论

发布
暂无评论
第八周作业