​

In this case, singly linked lists may have rings or no rings. Given the head nodes head1 and head2 of two single-linked lists, the two lists may or may not intersect. Implement a function that, if two lists intersect, returns the first node where they intersect; If it does not intersect, return NULL. Requirements: If the length of linked list 1 is N and the length of linked list 2 is M, the time complexity must reach O(N+M), extra

The space complexity must be O(1).

We divide the problem into four parts to discuss: 1. How to judge whether the linked list has a ring 2. Two acyclic lists intersect 3. Two acyclic lists intersect 4. One acyclic list and one acyclic list will not intersect, which is determined by the structure of single linked lists

Method 1: Use set

If there is a node that already exists, that node is the first one to intersect. Otherwise, if there is no same node until empty, it is acyclic (note: two nodes equal is equal memory address). Two acyclic lists, one of which is added to the set, and the other is added to the set at the same time. If one of the lists already exists, that is the first node to intersect. If there are no identical nodes, that is no intersection.

I’m not going to talk about it, but it’s not going to meet the spatial complexity requirements of the problem

Method 2:

​

* 1. Check whether the list has rings or not

* A list of more than three nodes is possible to form a ring * the fast pointer takes one step, the slow pointer takes two steps * as long as neither is null, when the two Pointers intersect, the fast pointer returns to the head pointer

* The fast pointer and the slow pointer both take one step, and when the two Pointers intersect again, the node is returned as the first intersecting node of the linked list

public static Node getLoopNode(Node head){ if(head==null || head.next==null || head.next.next==null){ return null; } Node slow = head.next; Node fast = head.next.next; while(slow! =fast){ if(fast.next == null || fast.next.next == null){ return null; } slow = slow.next; fast = fast.next.next; } fast = head; while(slow ! = fast){ fast = fast.next; slow = slow.next; } return slow; }Copy the code

* 2. Acyclic lists intersect

Len1,len2,end1,end2 * If two acyclic lists intersect, their tail must be the same (each node has only one successor). The long list goes first, and when it is as long as the short list, the two lists go together

* When two lists are equal, they intersect first

public static Node noLoop(Node head1,Node head2){ int len1 = 1,len2 = 1; Node end1 = head1; Node end2 = head2; while(end1.next! =null){ len1++; end1 = end1.next; } while(end2.next! =null){ len2++; end2 = end2.next; } if(end1! // If acyclic lists intersect, the last node must be the same node return null; } end1 = head1; End2 = head2; while(len1! =len2){ if(len1>len2){ len1--; end1 = end1.next; }else{ len2--; end2 = end2.next; }} // Now two lists go together while(end1! =end2){ end1 = end1.next; end2 = end2.next; } return end1; }Copy the code

* 3. There is a link list intersection

* There are three cases where two linked lists are looped * Case 1: two linked lists are looped separately and do not intersect * Case 2: two linked lists are looped together and do not intersect * Case 3: Two linked lists intersect first and then loop together. Two two lists each walk into the same ring * * fetch end1,end2 * if end1==end2, case 2 * if end1! =end2, case 2 or case 3 * in which case end1 goes all the way, and if it meets end2 * before it gets back to its entry point, that’s case 3, it intersects, otherwise it’s case 1, it doesn’t intersect * because it’s loop1, so end1 is loop1, and end2 is loop2

* End of process!

public static Node bothLoop(Node head1,Node head2,Node loop1,Node loop2){ Node cur1 = null; Node cur2 = null; if (loop1 == loop2) { cur1 = head1; cur2 = head2; int n = 0; while (cur1 ! = loop1) { n++; cur1 = cur1.next; } while (cur2 ! = loop2) { n--; cur2 = cur2.next; } // If n is greater than 0, then list 1 is longer, then set cur1 to the head of list 1 (otherwise, the same is also true). head1 : head2; Cur2 = cur1 == head1? head2 : head1; n = Math.abs(n); While (n-- > 0) {cur1 = cur1.next; } while (cur1 ! = cur2) { cur1 = cur1.next; cur2 = cur2.next; } return cur1; } else { cur1 = loop1.next; while (cur1 ! = loop1) { if (cur1 == loop2) { return loop1; } cur1 = cur1.next; } return null; }}Copy the code

Finally, call procedures and test cases:

public static class Node { public int value; public Node next; public Node(int value) { this.value = value; } } public static Node getIntersectNode(Node head1, Node head2) { if (head1 == null || head2 == null) { return null; } Node loop1 = getLoopNode(head1); Node loop2 = getLoopNode(head2); If (loop1 == null && loop2 == null) {return noLoop(head1, head2); if (loop1 == null && loop2 == null) {return noLoop(head1, head2); } if (loop1 ! = null && loop2 ! = null) { return bothLoop(head1, head2,loop1,loop2); } return null; }Copy the code

public static void main(String[] args) { // 1->2->3->4->5->6->7->null Node head1 = new Node(1); head1.next = new Node(2); head1.next.next = new Node(3); head1.next.next.next = new Node(4); head1.next.next.next.next = new Node(5); head1.next.next.next.next.next = new Node(6); head1.next.next.next.next.next.next = new Node(7); // 0->9->8->6->7->null Node head2 = new Node(0); head2.next = new Node(9); head2.next.next = new Node(8); head2.next.next.next = head1.next.next.next.next.next; // 8->6 System.out.println(getIntersectNode(head1, head2).value); / / 1 - > 2 - > 3 - > 4 - > 5 - > 6-7 - > > 4... head1 = new Node(1); head1.next = new Node(2); head1.next.next = new Node(3); head1.next.next.next = new Node(4); head1.next.next.next.next = new Node(5); head1.next.next.next.next.next = new Node(6); head1.next.next.next.next.next.next = new Node(7); head1.next.next.next.next.next.next = head1.next.next.next; 7 - > 4 / / / / 0-9 - > > 8 - > 2... head2 = new Node(0); head2.next = new Node(9); head2.next.next = new Node(8); head2.next.next.next = head1.next; // 8->2 System.out.println(getIntersectNode(head1, head2).value); / / 0-9 - > > 6-8 - > > 4 - > 5 - > 6.. head2 = new Node(0); head2.next = new Node(9); head2.next.next = new Node(8); head2.next.next.next = head1.next.next.next.next.next; // 8->6 System.out.println(getIntersectNode(head1, head2).value); // Answer: 6 2 4}Copy the code

​