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

How to judge whether the two linked lists intersect, I believe that many inexperienced people do not know what to do about it. Therefore, this paper summarizes the causes and solutions of the problem. Through this article, I hope you can solve this problem.

Given two single linked lists An and B, only two pointers are given. May I ask:

1. How to judge whether two simple linked lists (acyclic) intersect?

There are two desirable ways:

(1) artificially construct the ring, point the tail node of the linked list A to the linked list B, and then judge whether the ring is successful? Traverse down from the head pointer of the linked list B, and if you can return to B, it means the intersection

(2) determine whether the last node of the two linked lists is the same. If it intersects, the tail node must be the same node.

2. How to judge the intersection of two simple linked lists (I don't know if there is a ring)?

First judge whether there is a ring, judge whether there is a ring can use the chase method, set two pointers, one step, if you can meet, it means that there is a ring

(1) neither of them has a loop: back to question 1

(2) one has a ring and the other has no ring: there is no need to judge, it is certain that the two linked tables do not intersect.

(3) both have rings: determine whether the collision point of list An appears in the ring of list B, and if so, intersect. (when intersecting, the ring must be common to the two linked tables)

3. How to find the first intersection node of two intersecting linked lists (I don't know if there is a ring)?

Similarly, use the chase method to determine whether there is a ring and discuss it on a case-by-case basis.

(1) acyclic: artificially construct a ring and point the tail node of the linked list A to the linked list B to form a single linked list with a ring. This problem translates into finding a ring entry node with a ring single linked list.

Solution reference: connection point this

(2) Ring: calculate the length lA and lB of two linked lists (the sum of the length of the ring and the length from the ring to the entry point is the length of the linked list)

For calculating the length of linked list with links, please refer to http://blog.csdn.net/liuxialong/archive/2011/06/20/6555850.aspx

If lA > lB, the pointer An of the linked list goes to lA-lB first, and then the pointer of the linked list B starts to go, and the point where the two meet is the point of intersection.

If lB > lA, the pointer of list B goes to lB-lA first, and then the pointer of list A begins to go, and the point where the two meet is the point of intersection.

If there is a ring in the linked list, please also refer to whether there is a ring here.

After reading the above, have you mastered the method of how to judge whether two linked lists intersect? If you want to learn more skills or want to know more about it, you are welcome to follow the industry information channel, thank you for reading!

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.