On the eve of my senior year in computer science school,

The small grey that is applying for a job everywhere encountered the student with outstanding achievement of the same department rhubarb…

Gray said while recalling the interview last week…

There is a one-way linked list in which “rings” are possible, as shown below. How to use the program to determine whether this list is a linked list?

Method 1: Start from the beginning node and iterate through each node of the single linked list. Each time a new node is traversed, all nodes before the new node are traversed again from the new node, and the ID of the new node is compared with the ID of all nodes before this node. If all nodes before the new node have the same node ID, it indicates that the node has been traversed twice and the linked list has a ring. If the same node does not exist among all previous nodes, the next node is traversed and the operation is repeated.

For example, the linked list is as follows: A->B->C->D->B->C->D. When traversing node D, we need to compare the previous nodes A, B and C, and there is no same node. At this time, the next new node to be traversed is B. The nodes A, B, C and D before B also happen to have B, so B appears twice, and it can be judged that the linked list has A ring.

Suppose the distance from the head of the list to the entry point is D, and the ring length of the list is S. So the time complexity of the algorithm is 0+1+2+3+… .+(D+ s-1) = (D+ s-1)*(D+S)/2, which can be simply interpreted as O(N*N). This algorithm does not create additional storage space, and the space complexity can be simply understood as O(1).

Method 2: First create a HashSet with the node ID as the key to store the nodes that have been traversed. It then iterates through each node of the singly linked list, again starting from the beginning node. If the same node ID is found in the HashSet, then the linked list has a ring. If the same node ID does not exist in the HashSet, the new node ID is stored in the HashSet, and then the next node is entered. Go ahead and repeat.

This method is similar in flow to method 1, with the essential difference of using a HashSet as an additional cache.

Suppose the distance from the head of the list to the entry point is D, and the ring length of the list is S. The time complexity of each HashSet element lookup is O(1), so the overall time complexity is 1*(D+S)=D+S, which can be simply understood as O(N). The spatial complexity of the algorithm is D+ s-1, which can be simply understood as O(N).

Waiting for notice is no notice, which is the accepted language in the workplace.

These are the memories of xiao Grey’s tragedy…

Method 3: First create two Pointers 1 and 2 (in Java, two object references) that point to the first node of the list. We then begin a large loop, in which we move pointer 1 down one node at a time and pointer 2 down two nodes at a time, and compare whether the two Pointers point to the same node. If they are the same, then the linked list is judged to have a ring, if not, then continue the next cycle.

For example, in the linked list A->B->C->D->B->C->D, both Pointers initially point to node A and enter the first cycle, where pointer 1 moves to node B and pointer 2 moves to C. In the second cycle, pointer 1 moves to node C and pointer 2 moves to node B. In the third cycle, pointer 1 moves to node D, and pointer 2 moves to node D. At this time, the two Pointers point to the same node, and it can be judged that the linked list has a ring.

A more vivid example of this approach can also be used: on a circular track, two runners start from the same spot, one fast, the other slow. When two people run for some time, the faster runner will inevitably catch up and pass the slower runner again, simply because the track is circular.

Suppose the distance from the head of the list to the entry point is D, and the ring length of the list is S. So the cycle will go S times, which is simply O (N). No additional storage is used except for the two Pointers, so the space complexity is O (1).

Problem 1: judge whether two one-way linked lists intersect. If they do, find the intersection point.

Question 2: How to find the entry point of a linked list in a linked list?