Given two sorted linked lists l0, and l1, return a new sorted linked list containing the intersection of the two lists.
Constraints
n ≤ 100,000 where n is the number of nodes in l0
m ≤ 100,000 where m is the number of nodes in l1
Example 1
Input
l0 = [1, 3, 7]
l1 = [2, 3, 7, 9]
Output
[3, 7]Example 2
Input
l0 = [1, 2, 3]
l1 = [4, 5, 6]
Output
null
Linked List Intersection via Two Pointer Algorithm
Given two linked lists are already sorted, we can start comparing the head of both and move the small node one step forward or remember the equal (intersected) node.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | /** * class LLNode { * public: * int val; * LLNode *next; * }; */ LLNode* intersectionLinkedLists(LLNode* l0, LLNode* l1) { if (!l0) return nullptr; if (!l1) return nullptr; auto dummy = new LLNode(-1); auto p = dummy; while (l0 && l1) { if (l0->val == l1->val) { p->next = new LLNode(l0->val); l0 = l0->next; l1 = l1->next; p = p->next; } else if (l0->val < l1->val) { l0 = l0->next; } else { l1 = l1->next; } } return dummy->next; } |
/**
* class LLNode {
* public:
* int val;
* LLNode *next;
* };
*/
LLNode* intersectionLinkedLists(LLNode* l0, LLNode* l1) {
if (!l0) return nullptr;
if (!l1) return nullptr;
auto dummy = new LLNode(-1);
auto p = dummy;
while (l0 && l1) {
if (l0->val == l1->val) {
p->next = new LLNode(l0->val);
l0 = l0->next;
l1 = l1->next;
p = p->next;
} else if (l0->val < l1->val) {
l0 = l0->next;
} else {
l1 = l1->next;
}
}
return dummy->next;
} For linked lists algorithms, we can usually create a dummy head node so that we don’t need to handle the head node as a special case. The above linked list intersection algorithms runs at time complexity O(M+N) and space complexity O(M+N) where M and N are the lengths of two sorted linked lists respectively.
We can use the existing input linked list – to make it O(1) constant space.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | /** * class LLNode { * public: * int val; * LLNode *next; * }; */ LLNode* intersectionLinkedLists(LLNode* l0, LLNode* l1) { if (!l0) return nullptr; if (!l1) return nullptr; auto dummy = new LLNode(-1); auto p = dummy; while (l0 && l1) { if (l0->val == l1->val) { p->next = l0; // using the existing node l0 = l0->next; l1 = l1->next; p = p->next; } else if (l0->val < l1->val) { l0 = l0->next; } else { l1 = l1->next; } } p->next = nullptr; // make sure we truncate the last node's next return dummy->next; } |
/**
* class LLNode {
* public:
* int val;
* LLNode *next;
* };
*/
LLNode* intersectionLinkedLists(LLNode* l0, LLNode* l1) {
if (!l0) return nullptr;
if (!l1) return nullptr;
auto dummy = new LLNode(-1);
auto p = dummy;
while (l0 && l1) {
if (l0->val == l1->val) {
p->next = l0; // using the existing node
l0 = l0->next;
l1 = l1->next;
p = p->next;
} else if (l0->val < l1->val) {
l0 = l0->next;
} else {
l1 = l1->next;
}
}
p->next = nullptr; // make sure we truncate the last node's next
return dummy->next;
} See also: Teaching Kids Programming – Algorithms to Compute the Intersection of Two Linked Lists
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Teaching Kids Programming - Two Sum Algorithms
Next Post: Teaching Kids Programming - Breadth First Search Algorithm to Sum Root to Leaf Numbers in Binary Tree
