How to determine whether two linked lists have an intersection point, how to determine whether a sin

1.Determine if a linked list is intersecting?

Solution 1: Hash table method, maintain a hash table, and iterate through two linked lists respectively. The elements in them are stored in a hash table, and if the elements are duplicated, then the two linked lists intersect.

Solution 2: There is also a more imaginative solution, first iterate through the first linked list to its tail, and then point the next pointer at the tail to the second linked list (the next pointer at the tail originally pointed to null). In this way, the two linked lists are combined into a linked list, and determining whether the original two linked lists intersect becomes a question of determining whether the new linked list has a loop

That is, to determine whether a singly linked list has a ring?

In this way, after the conversion, you can judge from the header of the linked list, but it is not used. Through a simple understanding, it is easy to know that if the new linked list has a ring, then the head of the original second linked list must be on the ring. So we can traverse from the head of the second linked list, thus reducing the time complexity (the reduced time complexity is the length of the first linked list).

Solution 3: Study the two linked lists carefully, if they intersect, then their last node must be the same, otherwise it is disjoint. Therefore, it is very simple to determine whether two linked lists intersect, iterate to the tail of the two linked lists respectively, and then determine whether they are the same, and if they are the same, then intersect; Otherwise, they do not intersect.

2.If the intersection is found to be the intersection?

Solution 1: If you can allocate more memory, first traverse the linked list A, and add node to a hash table or binary tree when traversing the linked list A. Later, when traversing the node of linked list b, you can check whether the node has the corresponding position in the data structure.

It may be faster than the original method (which can be more expensive if the intersection is lower in the linked list, because of the need to maintain redundant data structures, so it is likely to be slower in practice than the original method), but it will use more memory space.

Solution 2: Traverse through two tables to know the lengths of the two tables a, b. Then let the long table go firsta-b|After the step, the short table starts to walk again until it is the same, and the first node of the same is the intersection point.

Linked lists 1 and 2 do not have rings.

Connect linked list 1 end to end to determine whether linked list 2 has a loop, and if so, intersect.

Basic idea 2:

Traverse through linked lists 1,2 and intersect if the tail pointers are equal.

If you want to subtract the absolute value of the length of linked list 1 and linked list 2, the longer linked list first moves the difference by one position, and then the two linked lists move at the same time, and the equal place is the intersection point. The algorithm is also not given.