Leetcode 160. Intersection of Two Linked Lists

Problem Explanation

The problem is to determine if two singly linked lists intersect, and if they do, return the first node from where the intersection begins. Each node in a singly linked list contains a value and a next pointer pointing to the next node in the link.

For instance, given two linked lists, A and B:

• A: 1 -> 2 -> 3 -> 4 -> 5

• B: 6 -> 7 -> 3 -> 4 -> 5

As you see, these lists intersect at the node with value 3 and continue being common till the end. Hence, our program should return the reference to the node with value 3.

If no intersection exists, the function should return null.

Keep in mind that:

• Linked lists must retain their original structure after the function returns.
• No cycles will exist in the entire linked structure.
• The function should ideally have a time complexity of O(n) and a space complexity of O(1).

Approach to the Solution

The approach of our solution will be based on two pointers technique. We will initiate two pointers, each at the head of both linked lists. Then, we will move these pointers one step at a time till they meet. If they meet, it means the linked list intersect and the meeting point is the start of intersection.

Let's see how it works with an example:

Say, we have two linked lists:

• A: 1 -> 2 -> 3 -> 4 -> 5

• B: 6 -> 7 -> 3 -> 4 -> 5

This is how pointers would move:

• a: 1 2 3 4 5 6 7 3 (found intersection)

• b: 6 7 3 4 5 1 2 3 (found intersection)

Now, let's see the implementation of this solution in multiple programming languages below.

Python Solution

1
2python
3class Solution:
4    def getIntersectionNode(self, headA, headB):
5        a, b = headA, headB
6
7        while a != b:
8            a = a.next if a else headB
9            b = b.next if b else headA
10
11        return a

Here, we first initialize two pointers a and b at head of Node A and B respectively. Then, until a and b meet or we reach end of both lists, we move pointers one step at a time. If a pointer reaches end of a list, we reset it to the head of the other list.

Java Solution

1
2java
3public class Solution {
4    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
5        ListNode a = headA;
6        ListNode b = headB;
7        
8        while (a != b) {
9            a = (a != null) ? a.next : headB;
10            b = (b != null) ? b.next : headA;
11        }
12        
13        return a;
14    }
15}

Javascript Solution

1
2javascript
3var getIntersectionNode = function(headA, headB) {
4    let a = headA, b = headB;  
5    while (a != b) {
6        a = a ? a.next : headB;
7        b = b ? b.next : headA;
8    }  
9    return a;
10};

C++ Solution

1
2cpp
3class Solution {
4public:
5    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
6        ListNode *a = headA, *b = headB;
7        while (a != b) {
8            a = a ? a->next : headB;
9            b = b ? b->next : headA;
10        }
11        return a;
12    }
13};

C# Solution

1
2csharp
3public class Solution {
4    public ListNode GetIntersectionNode(ListNode headA, ListNode headB) {
5        ListNode a = headA, b = headB;
6        while (a != b) {
7            a = a != null ? a.next : headB;
8            b = b != null ? b.next : headA;
9        }
10        return a;
11    }
12}

There you have it! A solution in Python, Java, Javascript, C++ and C# that finds the node at which the intersection of two singly linked lists begins or returns null if no intersection exist. Notice each function employs the two pointer technique and traverses each node in the linked lists at most twice, which results in O(n) time complexity. Not storing any additional data about the nodes results in O(1) space complexity.## Ruby Solution

This Ruby solution follows the same logic as the other languages.

1
2ruby
3class Solution
4    def getIntersectionNode(headA, headB)
5        a, b = headA, headB
6        while a != b
7            a.nil? ? a = headB : a = a.next
8            b.nil? ? b = headA : b = b.next
9        end
10        a
11    end
12end

Here, we initialize two pointers a and b at the head of headA and headB respectively. Then in a loop, we traverse through the linked lists. If a pointer reaches the end of a list, it is reset to the head of the other list. This continues until the pointers meet, signifying the intersection point, or if they both reach the end of their respective lists, signifying no intersection.

Swift Solution

1
2swift
3class Solution {
4    func getIntersectionNode(headA: ListNode?, headB: ListNode?) -> ListNode? {
5        var a = headA, b = headB
6        while a !== b {
7            a = a == nil ? headB : a?.next
8            b = b == nil ? headA : b?.next
9        }
10        return a
11    }
12}

This Swift solution initiates two optional pointers a and b at the head of headA and headB respectively. We then start a loop where we move these pointers one step at a time through their respective linked lists. Just like the previous solutions, each pointer switches to the head of the other list upon reaching the end of its list. This continues until the pointers are both nil, indicating no intersection, or the pointers are equal, indicating the intersection point.

Conclusion

In this article, we provided a solution to find the intersection of two singly linked lists in Python, Java, JavaScript, C++, C#, Ruby, and Swift. The algorithm uses the two pointer technique to compare each node in both lists, resulting in O(n) time complexity and O(1) space complexity. This technique ensures our solution is efficient and scalable for large inputs.