Shulou(Shulou.com)06/01 Report--

This article mainly shows you "java how to achieve intersection list", the content is easy to understand, clear, hope to help you solve your doubts, the following let the editor lead you to study and learn "how to achieve java intersection list" this article.

1. Title

Intersection list: give you two single-linked list header nodes headA and headB, please find and return two single-linked list intersection of the starting node. If the two linked lists do not intersect, return null. Intersecting linked list

two。 Analysis.

The intersecting linked list is Y-shaped and the next field is the same.

Define two references pl and ps

If the length of the intersection node of each linked list is the same, go step by step until the intersection node is found. If the length is not the same, you should first take the difference step in the long chain table, and then take one step until you meet.

The length is different:

The length is the same:

Let's first find the length, assuming that pl points to 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

Then, based on the positive or negative of the length difference, point the pl to the long linked list:

Int len = lenA-lenB;// difference step 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("不存在相交结点！"); } }

The above is all the contents of the article "how to achieve the intersection list in java". Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.