[Ninja Algorithm] Encountering the intersection of linked lists from intersections: Exploring the problem of intersecting linked lists | LeetCode Question 160 Intersecting linked lists

Encountering the intersection of linked lists from intersections: Exploring the problem of intersecting linked lists

Encountering problems in life

Imagine two people starting from different places and finally meeting at a crossroads. They may have traveled different lengths, but they will eventually converge at the same point. This is very similar to the intersecting linked list issue we are going to discuss today: two linked lists start from different starting points, intersect at a certain node, and then share subsequent paths.

Problem description

LeetCode Question 160 "Intersected Linked List" is described as follows: give you the head nodes of two single linked lists, headA and headB, please find and return the starting nodes of the two single linked lists. If the two linked lists do not have intersecting nodes, return null.

For example:

A link list: a1 → a2
                     ↘
                       c1 → c2 → c3
                     ↗
 B-link list: b1 → b2 → b3

 Output: Return to node c1

The most intuitive solution: hash table record

Just like marking where everyone walks in a city, the easiest way is to use a hash table to record all the places the first person walks, and then see if there are any duplications in the second person's path.

Implementation of hash table method

public class Solution {
     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
         // Use HashSet to record all nodes in linked list A
         Set<ListNode> visited = new HashSet<>();
        
         // traverse the linked list A and add nodes to the collection
         ListNode current = headA;
         while (current != null) {
             (current);
             current = ;
         }
        
         // traverse the linked list B and find the first node that appears in the collection
         current = headB;
         while (current != null) {
             if ((current)) {
                 return current;
             }
             current = ;
         }
        
         return null;
     }
 }

Optimization solution: Double pointer skills

After careful consideration, we found an interesting phenomenon: if two people walk each other's path separately, they will definitely meet in the end! This is the inspiration for the double-pointer solution.

The principle of the double pointer method

Imagine two people walking:

A starts from linked list A, and after finishing, turn to linked list B and continue walking
B starts from the linked list B, and after finishing, turn to the linked list A and continue walking
If the linked list intersects, they will definitely meet at the intersection point
- Because the total distance they have traveled is the same: length of linked list A + length of linked list B

Sample run

Suppose linked list A: 1→2→3→4, linked list B: 5→6→3→4 (3 is the intersection point)

Pointer A: 1 → 2 → 3 → 4 → 5 → 6 → [3] ← Encounter!
 Pointer B: 5 → 6 → 3 → 4 → 1 → 2 → [3] ← Encounter!

Java code implementation

public class Solution {
     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
         if (headA == null || headB == null) {
             return null;
         }
        
         // Initialize two pointers
         ListNode pointerA = headA;
         ListNode pointerB = headB;
        
         // Continue to move when the two pointers are not equal
         while (pointerA != pointerB) {
             // Move pointer A, if it reaches the end, it will go to linked list B
             pointerA = (pointerA == null) ? headB : ;
             // Move pointer B, if it reaches the end, it will go to linked list A
             pointerB = (pointerB == null) ? headA : ;
         }
        
         // Return the intersection point (if there is no intersection point, both pointers will be null)
         return pointerA;
     }
 }

Solution comparison

Let's compare these two methods:

Hash table method:

Time complexity: O(m+n)
Space complexity: O(m), m is the length of linked list A
Advantages: Intuitive thinking, easy to understand
Disadvantages: Additional storage nodes are required

Double pointer method:

Time complexity: O(m+n)
Space complexity: O(1)
Advantages: No extra space required, elegant and simple
Disadvantages: It's a little difficult to understand

Summary of practical skills

Key points to solve the problem of intersecting linked lists:

Understand that the intersecting nodes are shared
Consider special circumstances (such as empty linked lists, disjoint situations)
Make good use of double pointer skills
Utilize mathematical characteristics (the principle of equal distances)

summary

Through the intersecting linked list question, we learned how to skillfully use the double pointer technique to solve seemingly complex problems. This way of thinking can not only solve algorithm problems, but also be useful when dealing with practical problems such as data flow and file comparison. Remember, when encountering a problem that needs to find common elements of two sequences, the double pointer technique often provides an elegant solution!

Extended thinking:

If the linked list may have a loop, is this algorithm still valid?
If you want to find all the intersecting nodes, how should you modify the algorithm?
How to deal with similar "path intersecting" problems in distributed systems?

Author: Ninja Algorithm
Official account: Ninja Algorithm

🎯 Reply [Question List] Get more classic question analysis
👥 Reply [Add to Group] Join the algorithm/interview exchange group and learn and make progress together
🧑‍💻 Reply to [Code] to get the complete GitHub problem solution project, including Java/Python/JavaScript/Go/C++ multilingual implementation