java如何实现相交链表
这篇文章主要为大家展示了“java如何实现相交链表”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“java如何实现相交链表”这篇文章吧。
1.题目
相交链表：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。相交链表
2.分析
相交链表是Y字型，next域相同。
定义两个引用pl和ps，
如果每个链表相交结点前长度相同，一步一步走，直到相同就找到了相交结点。如果长度不一样，首先要长链表先走差值步，然后再一人走一步直到相遇
长度不同：
长度相同：
首先求长度，先假设pl指向headA：
ListNodepl=headA;ListNodeps=headB;intlenA=0;intlenB=0;while(pl!=null){lenA++;pl=pl.next;}//pl==null;pl=headA;while(ps!=null){lenB++;ps=ps.next;}//ps==null;ps=headB;
然后根据长度差值的正负判断谁长，将pl指向长的链表：
intlen=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;}returnpl;}
3.完整代码
//判断链表相交publicstaticListNodegetIntersectionNode(ListNodeheadA,ListNodeheadB){if(headA==null||headB==null){returnnull;}ListNodepl=headA;ListNodeps=headB;intlenA=0;intlenB=0;while(pl!=null){lenA++;pl=pl.next;}//pl==null;pl=headA;while(ps!=null){lenB++;ps=ps.next;}//ps==null;ps=headB;intlen=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;}returnpl;}
测试：
publicstaticvoidmain(String[]args){MyLinkedListmyLinkedList=newMyLinkedList();myLinkedList.addLast(12);myLinkedList.addLast(23);myLinkedList.addLast(34);myLinkedList.addLast(45);System.out.println("myLinkedList：");myLinkedList.display();MyLinkedListmyLinkedList1=newMyLinkedList();myLinkedList1.addLast(13);myLinkedList1.addLast(22);myLinkedList1.addLast(30);System.out.println("myLinkedList1：");myLinkedList1.display();createCut(myLinkedList.head,myLinkedList1.head);try{ListNoderet=getIntersectionNode(myLinkedList.head,myLinkedList1.head);myLinkedList.display2(ret);}catch(NullPointerExceptione){e.printStackTrace();System.out.println("没有相交结点！");}}
MyLinkedListmyLinkedList=newMyLinkedList();myLinkedList.addLast(12);myLinkedList.addLast(23);myLinkedList.addLast(34);myLinkedList.addLast(56);System.out.println("myLinkedList:");myLinkedList.display();MyLinkedListmyLinkedList1=newMyLinkedList();myLinkedList1.addLast(12);myLinkedList1.addLast(23);myLinkedList1.addLast(30);System.out.println("myLinkedList1:");myLinkedList1.display();//createCut(myLinkedList.head,myLinkedList1.head);try{ListNoderet=getIntersectionNode(myLinkedList.head,myLinkedList1.head);System.out.println(ret.val);}catch(NullPointerExceptione){e.printStackTrace();System.out.println("不存在相交结点！");}}
以上是“java如何实现相交链表”这篇文章的所有内容，感谢各位的阅读！相信大家都有了一定的了解，希望分享的内容对大家有所帮助，如果还想学习更多知识，欢迎关注恰卡编程网行业资讯频道！
