java|java 相交链表的实现示例 java相交链表的实现示例

1.题目
2.分析
3.完整代码

1.题目相交链表：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。相交链表

2.分析相交链表是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; }

3.完整代码

//判断链表相交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("不存在相交结点！"); }}