Given two linked list of size N1 and N2 respectively of distinct elements, your task is to complete the function countPairs(), which returns the count of all pairs from both lists whose sum is equal to the given value X.
Note: The 2 numbers of a pair should be parts of different lists.
Example 1:
Input:
L1 = 1->2->3->4->5->6
L2 = 11->12->13
X = 15
Output: 3
Explanation: There are 3 pairs that
add up to 15 : (4,11) , (3,12) and (2,13)
Example 2:
Input:
L1 = 7->5->1->3
L2 = 3->5->2->8
X = 10
Output: 2
Explanation: There are 2 pairs that add up
to 10 : (7,3) and (5,5)
Your Task:
You only need to implement the given function countPairs() and return the count.
Expected Time Complexity: O(N+M)
Expected Auxiliary Space: O(N+M)
Constraints:
1<=size of linked list<=10000
1<=X<=10000
Note : All elements in a linked list are unique.

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3

'''
class Node:
    def __init__(self, data):   # data -> value stored in node
        self.data = data
        self.next = None
'''
class Solution:
    def countPair(self,h1,h2,n1,n2,x):
        '''
        h1:  head of linkedList 1
        h2:  head of linkedList 2
        n1:  len of  linkedList 1
        n2:   len of linkedList 1
        X:   given sum
        '''

Solutions:
class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		dic1 = {}
		dic2 = {}
		count = 0
		while h1:
			if h1.data in dic1:
				dic1[h1.data] += 1
			else:
				dic1[h1.data] = 1
			h1 = h1.next
		while h2:
			if h2.data in dic2:
				dic2[h2.data] += 1
			else:
				dic2[h2.data] = 1
			h2 = h2.next
		for i in dic1:
			r = x - i
			if r in dic2:
				count += 1
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		dic1 = {}
		dic2 = {}
		ans = []
		while h1:
			if h1.data in dic1:
				dic1[h1.data] += 1
			else:
				dic1[h1.data] = 1
			h1 = h1.next
		while h2:
			if h2.data in dic2:
				dic2[h2.data] += 1
			else:
				dic2[h2.data] = 1
			h2 = h2.next
		for i in dic1:
			r = x - i
			if r in dic2:
				ans.append([i, r])
		return len(ans)


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		node1 = h1
		tmp = set()
		result = 0
		while node1:
			tmp.add(x - node1.data)
			node1 = node1.next
		node2 = h2
		while node2:
			if node2.data in tmp:
				result += 1
			node2 = node2.next
		return result


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		s = set([])
		while h1 != None:
			s.add(h1.data)
			h1 = h1.next
		c = 0
		while h2 != None:
			if x - h2.data in s:
				c += 1
			h2 = h2.next
		return c


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		temp1 = h1
		temp2 = h2
		temp = set()
		count = 0
		while temp1:
			temp.add(x - temp1.data)
			temp1 = temp1.next
		while temp2:
			if temp2.data in temp:
				count += 1
			temp2 = temp2.next
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		next_node1 = h1
		next_node2 = h2
		counter = 0
		lst1 = set()
		while next_node1:
			lst1.add(next_node1.data)
			next_node1 = next_node1.next
		while next_node2:
			if x - next_node2.data in lst1:
				counter += 1
			next_node2 = next_node2.next
		return counter


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		count = 0
		s = set()
		curr = h1
		while curr:
			s.add(curr.data)
			curr = curr.next
		curr = h2
		while curr:
			if x - curr.data in s:
				count += 1
			curr = curr.next
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		nums = {}
		temp = h1
		while temp:
			nums[temp.data] = 1
			temp = temp.next
		cnt = 0
		temp = h2
		while temp:
			if nums.get(x - temp.data):
				cnt += 1
			temp = temp.next
		return cnt


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		d1 = dict()
		d2 = dict()
		while h1 != None:
			d1[h1.data] = 0
			h1 = h1.next
		while h2 != None:
			d2[h2.data] = 0
			h2 = h2.next
		c = 0
		for i in d1:
			if x - i in d2:
				c += 1
		return c


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		node1 = h1
		node2 = h2
		set1 = set()
		while node1:
			set1.add(node1.data)
			node1 = node1.next
		count = 0
		while node2:
			if x - node2.data in set1:
				count += 1
			node2 = node2.next
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		dict1 = {}
		dict2 = {}
		temp1 = h1
		temp2 = h2
		for i in range(n1):
			if temp1.data not in dict1:
				dict1[temp1.data] = 1
			else:
				dict1[temp1.data] += 1
			temp1 = temp1.next
		for j in range(n2):
			if temp2.data not in dict2:
				dict2[temp2.data] = 1
			else:
				dict2[temp2.data] += 1
			temp2 = temp2.next
		pair_count = 0
		for item in dict1:
			ans = x - item
			try:
				if dict2[ans]:
					pair_count += 1
			except:
				pass
		return pair_count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		freq = {}
		while h1:
			if h1.data not in freq:
				freq[h1.data] = 0
			freq[h1.data] += 1
			h1 = h1.next
		c = 0
		while h2:
			if x - h2.data in freq:
				c += freq[x - h2.data]
			h2 = h2.next
		return c


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		count = 0
		us = set()
		while h1 != None:
			us.add(h1.data)
			h1 = h1.next
		while h2 != None:
			if x - h2.data in us:
				count += 1
			h2 = h2.next
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		l = set()
		temp = h1
		temp1 = h2
		c = 0
		while temp1:
			l.add(x - temp1.data)
			temp1 = temp1.next
		while temp:
			if temp.data in l:
				c += 1
			temp = temp.next
		return c


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		node1 = h1
		temp = set()
		cnt = 0
		while node1:
			temp.add(x - node1.data)
			node1 = node1.next
		node2 = h2
		while node2:
			if node2.data in temp:
				cnt += 1
			node2 = node2.next
		return cnt


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		if n1 > n2:
			(h1, h2) = (h2, h1)
		c = 0
		t1 = h1
		t2 = h2
		a = set()
		b = set()
		while t1:
			a.add(t1.data)
			t1 = t1.next
		while t2:
			b.add(t2.data)
			t2 = t2.next
		for i in a:
			if x - i in b and i != x:
				c += 1
		return c


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		if h1 is None or h2 is None:
			return 0
		count = 0
		mp = {}
		while h1:
			if h1.data not in mp:
				mp[h1.data] = 1
			h1 = h1.next
		while h2:
			if x - h2.data in mp:
				count += 1
			h2 = h2.next
		return count


class Solution:

	def countPair(self, a, b, n1, n2, x):
		co = 0
		d = {}
		while a:
			if a.data not in d:
				d[a.data] = 1
			else:
				d[a.data] += 1
			a = a.next
		while b:
			if x - b.data in d:
				co += d[x - b.data]
			b = b.next
		return co


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		s = set()
		temp = h1
		while temp is not None:
			s.add(temp.data)
			temp = temp.next
		counter = 0
		temp = h2
		while temp is not None:
			if x - temp.data in s:
				counter += 1
			temp = temp.next
		return counter


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		g = set()
		a = h1
		count = 0
		while a != None:
			g.add(a.data)
			a = a.next
		b = h2
		while b != None:
			s = x - b.data
			if s in g:
				count += 1
			b = b.next
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		diff = []
		p = h1
		while p != None:
			diff.append(x - p.data)
			p = p.next
		diff = set(diff)
		p = h2
		count = 0
		while p != None:
			if p.data in diff:
				count += 1
			p = p.next
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		d = dict()
		n = h1
		nn = h2
		c = 0
		while n != None:
			d[n.data] = n.data
			n = n.next
		while nn != None:
			if x - nn.data in d.keys():
				c += 1
			nn = nn.next
		return c


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		count = 0
		s = set()
		temp1 = h1
		temp2 = h2
		while temp2 is not None:
			s.add(x - temp2.data)
			temp2 = temp2.next
		while temp1 is not None:
			if temp1.data in s:
				count += 1
			temp1 = temp1.next
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		currentsum = 0
		pairset = set()
		if h1 is None or h2 is None:
			return False
		for _ in range(n1):
			pairset.add(h1.data)
			h1 = h1.next
		for _ in range(n2):
			if x - h2.data in pairset:
				currentsum += 1
			h2 = h2.next
		return currentsum


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		dt1 = {}
		dt2 = {}
		while h1:
			dt1[h1.data] = 1
			h1 = h1.next
		while h2:
			dt2[h2.data] = 1
			h2 = h2.next
		count = 0
		for i in dt1:
			if x - i in dt2:
				count += 1
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		ans = 0
		p1 = h1
		h11 = set()
		p2 = h2
		while p1:
			h11.add(p1.data)
			p1 = p1.next
		while p2:
			kk = p2.data
			if x - kk in h11:
				ans += 1
			p2 = p2.next
		return ans


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		arr = dict()
		temp = h1
		while temp:
			arr[x - temp.data] = 0
			temp = temp.next
		temp = h2
		r = 0
		while temp:
			if temp.data in arr:
				r += 1
			temp = temp.next
		return r


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		ct = set()
		c = 0
		temp = h1
		while temp:
			ct.add(x - temp.data)
			temp = temp.next
		ttwo = h2
		while ttwo:
			if ttwo.data in ct:
				c += 1
			ttwo = ttwo.next
		return c


def travrse(head, x):
	arr = set()
	while head:
		arr.add(x - head.data)
		head = head.next
	return arr

class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		a1 = travrse(h1, x)
		cnt = 0
		curr = h2
		while curr:
			if curr.data in a1:
				cnt += 1
			curr = curr.next
		return cnt


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		(s1, s2) = (set(), set())
		while h1:
			s1.add(h1.data)
			h1 = h1.next
		while h2:
			s2.add(h2.data)
			h2 = h2.next
		ans = 0
		for i in s1:
			if x - i in s2:
				ans += 1
		return ans


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		dic = {}
		while h1:
			dic[x - h1.data] = 1
			h1 = h1.next
		count = 0
		while h2:
			if h2.data in dic:
				count += 1
			h2 = h2.next
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		count = 0
		node = h1
		sett = set()
		while node:
			sett.add(node.data)
			node = node.next
		node = h2
		while node:
			if x - node.data in sett:
				count += 1
			node = node.next
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		l1 = set()
		t1 = h1
		t2 = h2
		c = 0
		while t1:
			l1.add(x - t1.data)
			t1 = t1.next
		while t2:
			if t2.data in l1:
				c += 1
			t2 = t2.next
		return c


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		(p1, p2) = (h1, h2)
		kmap = {}
		count = 0
		while p1:
			if p1.data not in kmap:
				kmap[p1.data] = 1
			p1 = p1.next
		while p2:
			if x - p2.data in kmap:
				count += 1
			p2 = p2.next
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		H = set()
		while h2 != None:
			H.add(h2.data)
			h2 = h2.next
		cnt = 0
		while h1 != None:
			if x - h1.data in H:
				cnt += 1
			h1 = h1.next
		return cnt


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		dic = {}
		temp = h1
		while temp != None:
			if temp.data in dic:
				dic[temp.data] += 1
			elif temp.data not in dic:
				dic[temp.data] = 1
			temp = temp.next
		count = 0
		while h2 != None:
			if x - h2.data in dic:
				count = count + dic[x - h2.data]
			h2 = h2.next
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		if h1 == None or h2 == None:
			return
		s1 = set()
		cur = h1
		while cur != None:
			s1.add(x - cur.data)
			cur = cur.next
		cur = h2
		cnt = 0
		while cur != None:
			if cur.data in s1:
				cnt += 1
			cur = cur.next
		return cnt


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		setti = set()
		while h1:
			setti.add(h1.data)
			h1 = h1.next
		count = 0
		while h2:
			count += x - h2.data in setti
			h2 = h2.next
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		a = 0
		p1 = h1
		p2 = h2
		hash = set()
		while p1:
			hash.add(x - p1.data)
			p1 = p1.next
		while p2:
			if p2.data in hash:
				a += 1
			p2 = p2.next
		return a


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		sum_count = 0
		t1 = h1
		t2 = h2
		temp = set()
		while t1:
			temp.add(x - t1.data)
			t1 = t1.next
		while t2:
			if t2.data in temp:
				sum_count += 1
			t2 = t2.next
		return sum_count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		l = set()
		t1 = h1
		while t1:
			l.add(t1.data)
			t1 = t1.next
		count = 0
		t2 = h2
		while t2:
			if x - t2.data in l:
				count = count + 1
			t2 = t2.next
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		s1 = set()
		tmp = h1
		while tmp:
			s1.add(tmp.data)
			tmp = tmp.next
		c = 0
		tmp = h2
		while tmp:
			if x - tmp.data in s1:
				c += 1
			tmp = tmp.next
		return c


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		mapp1 = set()
		cur1 = h1
		while cur1:
			mapp1.add(cur1.data)
			cur1 = cur1.next
		mapp2 = set()
		cur2 = h2
		while cur2:
			mapp2.add(cur2.data)
			cur2 = cur2.next
		count = 0
		cur = h2
		while cur:
			if x - cur.data in mapp1:
				count += 1
			cur = cur.next
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		myset = set()
		while h1 != None:
			myset.add(h1.data)
			h1 = h1.next
		ans = 0
		while h2 != None:
			if x - h2.data in myset:
				ans += 1
			h2 = h2.next
		return ans


class Solution:

	def countPair(self, head1, head2, n1, n2, x):
		primeequalcount = 0
		dicting = dict()
		while head1 != None:
			dicting[head1.data] = True
			head1 = head1.next
		while head2 != None:
			find = x - head2.data
			if dicting.get(find):
				primeequalcount += 1
			head2 = head2.next
		return primeequalcount


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		val_m = set()
		while h1 != None:
			val_m.add(h1.data)
			h1 = h1.next
		result = 0
		while h2 != None:
			target = x - h2.data
			if target in val_m:
				result += 1
			h2 = h2.next
		return result


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		from collections import defaultdict
		if h1 is None or h2 is None:
			return 0
		(curr1, curr2) = (h1, h2)
		nums1 = []
		nums2 = []
		while curr1 is not None:
			nums1.append(curr1.data)
			curr1 = curr1.next
		while curr2 is not None:
			nums2.append(curr2.data)
			curr2 = curr2.next
		freq = defaultdict(lambda : 0)
		for num in nums1:
			freq[x - num] += 1
		count = 0
		for num in nums2:
			if num in freq and freq[num] != 0:
				count += 1
				freq[num] -= 1
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		set1 = set()
		(tmpHead1, tmpHead2) = (h1, h2)
		count = 0
		while tmpHead1:
			set1.add(x - tmpHead1.data)
			tmpHead1 = tmpHead1.next
		while tmpHead2:
			if tmpHead2.data in set1:
				count += 1
			tmpHead2 = tmpHead2.next
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		p = h1
		q = h2
		l = set()
		c = 0
		while p:
			l.add(x - p.data)
			p = p.next
		while q:
			m = q.data
			if m in l:
				c += 1
			q = q.next
		return c


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		m2 = {}
		c = 0
		while h2:
			if h2.data in m2:
				m2[h2.data] += 1
			else:
				m2[h2.data] = 1
			h2 = h2.next
		while h1:
			if x - h1.data in m2:
				c += 1
			h1 = h1.next
		return c


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		from collections import defaultdict
		m1 = defaultdict(int)
		m2 = defaultdict(int)
		while h1:
			m1[h1.data] += 1
			h1 = h1.next
		while h2:
			m2[h2.data] += 1
			h2 = h2.next
		sm = 0
		for i in m1:
			sm += m2[x - i] * m1[i]
		return sm


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		curr1 = h1
		curr2 = h2
		s = set()
		count = 0
		while curr1 != None:
			s.add(x - curr1.data)
			curr1 = curr1.next
		while curr2 != None:
			if curr2.data in s:
				count += 1
			curr2 = curr2.next
		return count


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		d = {}
		c = 0
		if h1:
			temp = h1
			while temp:
				if temp.data not in d:
					d[temp.data] = 1
				else:
					d[temp.data] += 1
				temp = temp.next
		if h2:
			temp = h2
			while temp:
				a = abs(x - temp.data)
				if a in d:
					if d[a] > 0:
						if a + temp.data == x:
							c += 1
							d[a] -= 1
				temp = temp.next
		return c


from itertools import product

class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		li1 = set()
		c = 0
		while h2:
			li1.add(x - h2.data)
			h2 = h2.next
		while h1:
			if h1.data in li1:
				c += 1
			h1 = h1.next
		return c


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		c = 0
		res1 = {}
		ind = -1
		while h1:
			res1[x - h1.data] = x - h1.data
			h1 = h1.next
		while h2:
			if h2.data in res1.keys():
				c += 1
			h2 = h2.next
		return c


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		k = {}
		temp = h1
		while temp:
			k[x - temp.data] = 1
			temp = temp.next
		ct = 0
		temp2 = h2
		while temp2:
			if temp2.data in k.keys():
				ct += 1
			temp2 = temp2.next
		return ct


class Solution:

	def countPair(self, h1, h2, n1, n2, x):
		fi = h1
		se = h2
		ct = 0
		s = set()
		while se:
			s.add(x - se.data)
			se = se.next
		while fi:
			if fi.data in s:
				ct += 1
			fi = fi.next
		return ct