这篇文章主要为大家展示了“java如何实现相交链表”,内容简而易懂,条理清晰,希望能够帮助大家解决疑惑,下面让小编带领大家一起研究并学习一下“java如何实现相交链表”这篇文章吧。
相交链表:给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回 null 。相交链表
相交链表是Y字型
,next域
相同。
定义两个引用pl和ps
,
如果每个链表相交结点前长度相同,一步一步走,直到相同就找到了相交结点。如果长度不一样,首先要长链表先走差值步,然后再一人走一步直到相遇
长度不同:
长度相同:
首先求长度,先假设pl指向headA:
ListNode pl = headA;
ListNode ps = headB;
int lenA = 0;
int lenB = 0;
while (pl != null) {
lenA++;
pl = pl.next;
}
//pl==null;
pl = headA;
while (ps != null) {
lenB++;
ps = ps.next;
}
//ps==null;
ps = headB;
然后根据长度差值的正负判断谁长,将pl指向长的链表:
int len = lenA - lenB;//差值步
if (len < 0) {
pl = headB;
ps = headA;
len = lenB - lenA;
}
然后长的先走长度差值步,最后一人一步走:
//pl走差值len步
while (len != 0) {
pl = pl.next;
len--;
}
//同时走,直到相遇
while (pl != ps) {
pl = pl.next;
ps = ps.next;
}
return pl;
}
//判断链表相交
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pl = headA;
ListNode ps = headB;
int lenA = 0;
int lenB = 0;
while (pl != null) {
lenA++;
pl = pl.next;
}
//pl==null;
pl = headA;
while (ps != null) {
lenB++;
ps = ps.next;
}
//ps==null;
ps = headB;
int len = lenA - lenB;//差值步
if (len < 0) {
pl = headB;
ps = headA;
len = lenB - lenA;
}
//1、pl永远指向最长的链表 ps永远指向最短的链表 2、求到了差值len步
//pl走差值len步
while (len != 0) {
pl = pl.next;
len--;
}
//同时走,直到相遇
while (pl != ps) {
pl = pl.next;
ps = ps.next;
}
return pl;
}
测试:
public static void main(String[] args) {
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addLast(12);
myLinkedList.addLast(23);
myLinkedList.addLast(34);
myLinkedList.addLast(45);
System.out.println("myLinkedList:");
myLinkedList.display();
MyLinkedList myLinkedList1 = new MyLinkedList();
myLinkedList1.addLast(13);
myLinkedList1.addLast(22);
myLinkedList1.addLast(30);
System.out.println("myLinkedList1:");
myLinkedList1.display();
createCut(myLinkedList.head, myLinkedList1.head);
try {
ListNode ret = getIntersectionNode(myLinkedList.head, myLinkedList1.head);
myLinkedList.display2(ret);
} catch (NullPointerException e) {
e.printStackTrace();
System.out.println("没有相交结点!");
}
}
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addLast(12);
myLinkedList.addLast(23);
myLinkedList.addLast(34);
myLinkedList.addLast(56);
System.out.println("myLinkedList:");
myLinkedList.display();
MyLinkedList myLinkedList1 = new MyLinkedList();
myLinkedList1.addLast(12);
myLinkedList1.addLast(23);
myLinkedList1.addLast(30);
System.out.println("myLinkedList1:");
myLinkedList1.display();
//createCut(myLinkedList.head,myLinkedList1.head);
try {
ListNode ret = getIntersectionNode(myLinkedList.head, myLinkedList1.head);
System.out.println(ret.val);
}catch (NullPointerException e){
e.printStackTrace();
System.out.println("不存在相交结点!");
}
}
以上是“java如何实现相交链表”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!
亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。