第八周作业
发布于: 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; }
划线
评论
复制
发布于: 2020 年 11 月 15 日阅读数: 23
Geek_ac4080
关注
还未添加个人签名 2019.05.09 加入
还未添加个人简介
评论