Write a program to find the node at which the intersection of two singly linked lists begins. For example, the following two linked lists: A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3 begin to intersect at node c1. Notes: If the two linked lists have no intersection at all, return null. The linked lists must retain their original structure after the function returns. You may assume there are no cycles anywhere in the entire linked structure. Your code should preferably run in O(n) time and use only O(1) memory. **Credits:**Special thanks to @stellari for adding this problem and creating all test cases. Subscribe to see which companies asked this question.
The title
Write a program to find the intersecting nodes at the beginning of two singly linked lists. ** If two lists are not crossed, null is returned. After the result is returned, both lists must remain in their original structure. It can be assumed that there are no loops in the entire list structure. The following two linked lists are examples:
Analysis of the
There are two ways to solve this problem. The easiest way to solve this problem is to find the length of two lists, AB, and find the difference between them, and then the longer one starts at the point where the strength is subtracted, and then the two lists increase at the same time, and they meet the same node, which is the crossover node.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param headA: the first list
* @param headB: the second list
* @return: a ListNode
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
int alen = getlen(headA);
int blen = getlen(headB);
if(alen > blen)
return helper(headA,headB,alen-blen);
else
return helper(headB,headA,blen-alen);
}
private ListNode helper(ListNode headA, ListNode headB, int n) {
while(n>0) {
headA = headA.next;
n--;
}
while(headA ! = headB) { headA = headA.next; headB = headB.next; }return headA;
}
private int getlen(ListNode head) {
int len=0;
while(head ! = null) { len++; head = head.next; }returnlen; }}Copy the code
The second solution is to use the looped list problem. We connect the tail of the first list to the head of the second list, which naturally becomes a looped list. Then the problem is to find the starting node of the looped list, which can be referred to the problem of looped list II. Alter table struct; alter table struct;
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
/**
* @param headA: the first list
* @param headB: the second list
* @return: a ListNode
*/
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
// get the tail of list A.
ListNode node = headA;
while(node.next ! = null) { node = node.next; } node.next = headB; ListNode result = listCycleII(headA); node.next = null;return result;
}
private ListNode listCycleII(ListNode head) {
ListNode slow = head, fast = head.next;
while(slow ! = fast) {if (fast == null || fast.next == null) {
return null;
}
slow = slow.next;
fast = fast.next.next;
}
slow = head;
fast = fast.next;
while(slow ! = fast) { slow = slow.next; fast = fast.next; }returnslow; }}Copy the code
The third solution is hash table
The answer is to store one linked list in the hash table, iterate through the other, and find the first node in the hash table
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
Set<ListNode> setA = new HashSet<>();
while(headA ! = null) {setA.add(headA);
headA = headA.next;
}
while(headB ! = null) {if(setA.contains(headB))
return headB;
headB = headB.next;
}
return null;
}
Copy the code