Given two string, represented as linked lists (every character is a node->data in the linked list). Write a function compare() that works similar to strcmp(), i.e., it returns 0 if both strings are same, 1 if first linked list is lexicographically greater, and -1 if second is lexicographically greater.
Input:
First line of input contains number of testcases T. For each testcase, there will be 4 lines of input. First line of which contains length of first linked list and next line contains the linked list, similarly next two lines contains length and linked list respectively.
Output:
Comapare two strings represented as linked list.
User Task:
The task is to complete the function compare() which compares the strings through linked list and returns 0, 1 or -1 accordingly.
Constraints:
1 <= T <= 100
1 <= N, M <= 100
Example:
Input:
2
5
a b a b a
4
a b a a
3
a a b
3
a a b
Output:
1
0
Explanation:
Testcase 1: String consisting of nodes of first linked list is lexicographically greater than the second one. So, the result is 1.

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



'''

class Node:

    def __init__(self,data):

        self.data=data

        self.next=None

'''

def compare(head1, head2):

    #return 1/-1/0

Solutions:
def compare(head1, head2):
	s = ''
	p = ''
	while head1:
		s += head1.data
		head1 = head1.next
	while head2:
		p += head2.data
		head2 = head2.next
	if s == p:
		return '0'
	elif s > p:
		return '1'
	else:
		return '-1'


def compare(head1, head2):
	n = head1
	nn = head2
	op = 0
	c = 0
	while n.next or nn.next:
		if n.data == nn.data:
			op = 0
		if ord(nn.data) > ord(n.data):
			op = -1
			if c == 0:
				return -1
		if ord(nn.data) < ord(n.data):
			op = 1
			if c == 0:
				return 1
		n = n.next
		if n == None:
			break
		nn = nn.next
		if nn == None:
			break
	return op


def compare(head1, head2):
	n = head1
	s1 = ''
	while n is not None:
		s1 = s1 + n.data
		n = n.next
	n = head2
	s2 = ''
	while n is not None:
		s2 = s2 + n.data
		n = n.next
	if s1 == s2:
		return 0
	elif s1 > s2:
		return 1
	else:
		return -1


def compare(head1, head2):
	a = head1
	s = ''
	while a is not None:
		s += a.data
		a = a.next
	b = head2
	m = ''
	while b is not None:
		m += b.data
		b = b.next
	if s == m:
		return 0
	elif s > m:
		return 1
	return -1


def compare(head1, head2):
	a = []
	b = []
	while head1 != None:
		a.append(head1.data)
		head1 = head1.next
	while head2 != None:
		b.append(head2.data)
		head2 = head2.next
	if a > b:
		return 1
	elif b > a:
		return -1
	else:
		return 0


def compare(head1, head2):
	p = head1
	q = head2
	while p or q:
		if ord(p.data) < ord(q.data):
			return -1
		elif ord(p.data) > ord(q.data):
			return 1
		else:
			p = p.next
			q = q.next
	if p == None and q == None:
		return 0
	if p == None:
		return -1
	else:
		return 1


def compare(head1, head2):
	temp1 = head1
	temp2 = head2
	while temp1 != None and temp2 != None:
		if temp1.data > temp2.data:
			return 1
		if temp1.data < temp2.data:
			return -1
		temp1 = temp1.next
		temp2 = temp2.next
	if temp1 == None and temp2 == None:
		return 0


def compare(head1, head2):
	while head1 and head2:
		if head1.data == head2.data:
			head1 = head1.next
			head2 = head2.next
		elif head1.data > head2.data:
			return 1
		else:
			return -1
	if head1:
		return 1
	elif head2:
		return -1
	return 0


def compare(head1, head2):
	if not head1 and (not head2):
		return 0
	if not head1 and head2:
		return -1
	if head1 and (not head2):
		return 1
	if head1.data != head2.data:
		if head1.data > head2.data:
			return 1
		else:
			return -1
	return compare(head1.next, head2.next)


def compare(head1, head2):
	(cur1, cur2) = (head1, head2)
	while cur1 and cur2:
		if ord(cur1.data) > ord(cur2.data):
			return 1
		elif ord(cur1.data) < ord(cur2.data):
			return -1
		else:
			cur1 = cur1.next
			cur2 = cur2.next
	if cur1 != None:
		return 1
	elif cur2 != None:
		return -1
	else:
		return 0


def compare(head1, head2):
	(ptr1, ptr2) = (head1, head2)
	while ptr1 and ptr2:
		if ptr1.data > ptr2.data:
			return 1
		elif ptr2.data > ptr1.data:
			return -1
		ptr1 = ptr1.next
		ptr2 = ptr2.next
	if not ptr1 and (not ptr2):
		return 0
	if ptr1:
		return 1
	return -1


def compare(head1, head2):
	s1 = ''
	s2 = ''
	ptr = head1
	while ptr:
		s1 += str(ptr.data)
		ptr = ptr.next
	ptr = head2
	while ptr:
		s2 += str(ptr.data)
		ptr = ptr.next
	if s1 > s2:
		return 1
	elif s1 == s2:
		return 0
	else:
		return -1


def compare(head1, head2):
	stack1 = [head1]
	stack2 = [head2]
	while len(stack1) > 0 or len(stack2) > 0:
		current1 = stack1.pop()
		current2 = stack2.pop()
		if current1.data == current2.data:
			if current1.next and current2.next:
				stack1.append(current1.next)
				stack2.append(current2.next)
			elif current1.next and current2.next == None:
				return 1
			elif current1.next == None and current2.next:
				return -1
			else:
				return 0
		elif current1.data > current2.data:
			return 1
		else:
			return -1


def compare(head1, head2):
	n = head1
	m = head2
	while n != None and m != None:
		if n.data > m.data:
			return 1
		elif m.data > n.data:
			return -1
		n = n.next
		m = m.next
	if n != None:
		return 1
	elif m != None:
		return -1
	else:
		return 0


def compare(head1, head2):
	str1 = ''
	str2 = ''
	while head1:
		str1 += str(head1.data)
		head1 = head1.next
	while head2:
		str2 += str(head2.data)
		head2 = head2.next
	if str1 == str2:
		return '0'
	elif str1 > str2:
		return '1'
	else:
		return '-1'


def compare(head1, head2):
	s1 = ''
	s2 = ''
	while head1:
		s1 += head1.data
		head1 = head1.next
	while head2:
		s2 += head2.data
		head2 = head2.next
	if s1 == s2:
		return 0
	if s1 > s2:
		return 1
	else:
		return -1


def compare(head1, head2):
	while head1 and head2:
		if head1.data > head2.data:
			return 1
		if head2.data > head1.data:
			return -1
		head1 = head1.next
		head2 = head2.next
	if not (head1 or head2):
		return 0
	if head1:
		return 1
	return -1


def traverse(head):
	cur = head
	p = ''
	while cur:
		p += cur.data
		cur = cur.next
	return p

def compare(head1, head2):
	str1 = traverse(head1)
	str2 = traverse(head2)
	if str1 == str2:
		return 0
	else:
		for i in range(min(len(str1), len(str2))):
			if str1[i] < str2[i]:
				return -1
			elif str1[i] > str2[i]:
				return 1
		return -1


def compare(head1, head2):
	s1 = []
	s2 = []
	while head1:
		s1.append(head1.data)
		head1 = head1.next
	while head2:
		s2.append(head2.data)
		head2 = head2.next
	l1 = ''.join(s1)
	l2 = ''.join(s2)
	if l1 == l2:
		return 0
	elif l1 < l2:
		return -1
	return 1


def compare(head1, head2):
	b = []
	c = []
	tmp1 = head1
	tmp2 = head2
	while tmp1 != None:
		b.append(tmp1.data)
		tmp1 = tmp1.next
	while tmp2 != None:
		c.append(tmp2.data)
		tmp2 = tmp2.next
	if b > c:
		return 1
	elif c > b:
		return -1
	if b == c:
		return 0


def compare(head1, head2):
	ptr = head1
	ptr1 = head2
	while ptr and ptr1:
		if ptr.data > ptr1.data:
			return 1
		elif ptr.data < ptr1.data:
			return -1
		ptr = ptr.next
		ptr1 = ptr1.next
	return 0


def compare(head1, head2):
	arr1 = []
	while head1 != None:
		arr1.append(head1.data)
		head1 = head1.next
	arr2 = []
	while head2 != None:
		arr2.append(head2.data)
		head2 = head2.next
	if arr1 == arr2:
		return 0
	if arr1 > arr2:
		return 1
	return -1


def compare(head1, head2):
	a = ''
	b = ''
	t = head1
	r = head2
	while t:
		a += t.data
		t = t.next
	while r:
		b += r.data
		r = r.next
	if a == b:
		return 0
	elif a > b:
		return 1
	return -1


def compare(head1, head2):
	s1 = ''
	s2 = ''
	temp = head1
	while temp:
		s1 = s1 + temp.data
		temp = temp.next
	te = head2
	while te:
		s2 = s2 + te.data
		te = te.next
	if s1 == s2:
		return 0
	elif s1 > s2:
		return 1
	else:
		return -1


def compare(head1, head2):
	p1 = head1
	p2 = head2
	s1 = ''
	s2 = ''
	while p1:
		s1 += p1.data
		p1 = p1.next
	while p2:
		s2 += p2.data
		p2 = p2.next
	if s1 == s2:
		return 0
	elif s1 > s2:
		return 1
	else:
		return -1


def compare(head1, head2):
	l1 = []
	l2 = []
	while head1:
		l1.append(head1.data)
		head1 = head1.next
	while head2:
		l2.append(head2.data)
		head2 = head2.next
	s1 = ''
	s2 = ''
	for i in l1:
		s1 = s1 + i
	for j in l2:
		s2 = s2 + j
	if s1 == s2:
		return 0
	if s1 > s2:
		return 1
	return -1


def compare(head1, head2):
	while head1 and head2:
		if head1.data < head2.data:
			return -1
		elif head1.data > head2.data:
			return 1
		elif head1.data == head2.data:
			pass
		head1 = head1.next
		head2 = head2.next
	if head1 != None:
		return 1
	if head2 != None:
		return -1
	return 0


def compare(head1, head2):
	ptr = head1
	ptr2 = head2
	flag = 0
	while ptr is not None:
		if ptr2 is not None and ptr.data != ptr2.data:
			flag = 0
			break
		else:
			flag = 1
			ptr2 = ptr2.next
			ptr = ptr.next
	if flag == 1:
		return 0
	while ptr is not None and ptr2 is not None:
		if ptr.data > ptr2.data:
			return 1
		elif ptr.data < ptr2.data:
			return -1
		else:
			ptr2 = ptr2.next
			ptr = ptr.next


def compare(head1, head2):
	flag = False
	while head1 or head2:
		if head1.data != head2.data:
			flag = True
		if ord(head1.data) > ord(head2.data):
			return 1
		if ord(head1.data) < ord(head2.data):
			return -1
		head1 = head1.next
		head2 = head2.next
	if flag == False:
		return 0


def compare(head1, head2):
	temp1 = head1
	temp2 = head2
	length1 = 0
	length2 = 0
	while temp1 != None and temp2 != None:
		if temp1.data > temp2.data:
			return 1
		if temp2.data > temp1.data:
			return -1
		temp1 = temp1.next
		temp2 = temp2.next
	if temp1 == None and temp2 != None:
		return -1
	if temp2 == None and temp1 != None:
		return 1
	else:
		return 0


def compare(head1, head2):
	l1 = ''
	l2 = ''
	ptr1 = head1
	ptr2 = head2
	while ptr1:
		l1 += str(ptr1.data)
		ptr1 = ptr1.next
	while ptr2:
		l2 += str(ptr2.data)
		ptr2 = ptr2.next
	if l1 == l2:
		return 0
	elif l1 > l2:
		return 1
	else:
		return -1


def compare(head1, head2):
	temp1 = head1
	temp2 = head2
	while temp1 or temp2:
		if ord(temp1.data) > ord(temp2.data):
			return 1
		if ord(temp1.data) < ord(temp2.data):
			return -1
		temp1 = temp1.next
		temp2 = temp2.next
	return 0


def compare(head1, head2):
	while head1 or head2:
		if head1.data == head2.data:
			head1 = head1.next
			head2 = head2.next
		elif head1.data > head2.data:
			return 1
		else:
			return -1
	if head1 is None and head2 is None:
		return 0
	elif head2 is None:
		return 1
	else:
		return -1


def compare(head1, head2):
	tmp1 = head1
	tmp2 = head2
	while tmp1 or tmp2:
		if tmp1.data > tmp2.data or tmp2 == None:
			return 1
		elif tmp1.data < tmp2.data or tmp1 == None:
			return -1
		tmp1 = tmp1.next
		tmp2 = tmp2.next
	return 0


def compare(head1, head2):
	str1 = ''
	str2 = ''
	while head1 != None:
		str1 = str1 + head1.data
		head1 = head1.next
	while head2 != None:
		str2 = str2 + head2.data
		head2 = head2.next
	if str1 > str2:
		return 1
	elif str2 > str1:
		return -1
	return 0


def compare(head1, head2):
	t1 = head1
	t2 = head2
	while t1 != None and t2 != None:
		if t1.data > t2.data:
			return 1
		elif t2.data > t1.data:
			return -1
		t1 = t1.next
		t2 = t2.next
	if t1 != None and t2 == None:
		return 1
	elif t1 == None and t2 != None:
		return -1
	else:
		return 0


import string

def compare(head1, head2):
	s = string.ascii_lowercase
	l = list(s)
	d = {}
	i = 1
	for j in l:
		d[j] = i
		i += 1
	if head1 and head2:
		t1 = head1
		t2 = head2
		while t1 and t2:
			t1.data.lower()
			t2.data.lower()
			if d[t1.data] == d[t2.data]:
				t1 = t1.next
				t2 = t2.next
			elif d[t1.data] > d[t2.data]:
				return 1
			else:
				return -1
		return 0
	if head1 and (not head2):
		return 1
	if head2 and (not head1):
		return -1


def compare(head1, head2):
	s1 = ''
	s2 = ''
	p = head1
	q = head2
	while p:
		s1 += p.data
		p = p.next
	while q:
		s2 += q.data
		q = q.next
	if s1 == s2:
		return 0
	elif s1 > s2:
		return 1
	else:
		return -1


def compare(head1, head2):
	temp1 = head1
	temp2 = head2
	temp3 = head1
	temp4 = head2
	count = 0
	k = 0
	while temp1 is not None:
		count += 1
		temp1 = temp1.next
	while temp3 is not None and temp4 is not None:
		if temp3.data > temp4.data:
			return 1
		elif temp3.data < temp4.data:
			return -1
		else:
			k += 1
		temp3 = temp3.next
		temp4 = temp4.next
	if k == count:
		return 0


def compare(head1, head2):
	cur1 = head1
	cur2 = head2
	curt = head1
	c1 = 0
	k = 0
	while curt is not None:
		c1 += 1
		curt = curt.next
	while cur1 != None and cur2 != None:
		if cur1.data > cur2.data:
			return 1
		elif cur2.data > cur1.data:
			return -1
		elif cur1.data == cur2.data:
			k += 1
		cur1 = cur1.next
		cur2 = cur2.next
	if k == c1:
		return 0


def compare(head1, head2):
	cur1 = head1
	cur2 = head2
	cur1_ar = []
	cur2_ar = []
	K = True
	while cur1 and cur2:
		if cur1.data != cur2.data:
			K = False
		cur1_ar.append(ord(cur1.data))
		cur2_ar.append(ord(cur2.data))
		cur1 = cur1.next
		cur2 = cur2.next
	if K:
		return 0
	else:
		len1 = len(cur1_ar)
		len2 = len(cur2_ar)
		maxi = max(len1, len2)
		for i in range(maxi):
			if i < len(cur1_ar) and i < len(cur2_ar):
				if cur1_ar[i] > cur2_ar[i]:
					return 1
				elif cur1_ar[i] == cur2_ar[i]:
					continue
				else:
					return -1
			else:
				break
		if maxi == len1:
			return 1
		else:
			return -1


def compare(head1, head2):
	temp1 = head1
	temp2 = head2
	while temp1 is not None and temp2 is not None:
		if temp1.data > temp2.data:
			return 1
		elif temp1.data < temp2.data:
			return -1
		temp1 = temp1.next
		temp2 = temp2.next
	if temp1 is not None:
		return 1
	elif temp2 is not None:
		return -1
	else:
		return 0


def compare(head1, head2):
	(temp1, temp2) = (head1, head2)
	while temp1 and temp2:
		v1 = temp1.data if temp1 else None
		v2 = temp2.data if temp2 else None
		if v1 > v2:
			return 1
		elif v2 > v1:
			return -1
		temp1 = temp1.next
		temp2 = temp2.next
	if temp1:
		return 1
	if temp2:
		return -1
	return 0


def compare(head1, head2):
	curr1 = head1
	s1 = ''
	while curr1 != None:
		s1 += curr1.data
		curr1 = curr1.next
	curr1 = head2
	s2 = ''
	while curr1 != None:
		s2 += curr1.data
		curr1 = curr1.next
	if s1 > s2:
		return 1
	if s2 > s1:
		return -1
	return 0


def compare(head1, head2):
	t1 = ''
	t2 = ''
	while head1:
		t1 += head1.data
		head1 = head1.next
	while head2:
		t2 += head2.data
		head2 = head2.next
	if t1 == t2:
		return 0
	if t1 > t2:
		return 1
	return -1


def compare(head1, head2):
	l = []
	m = []
	while head1:
		l.append(head1.data)
		head1 = head1.next
	while head2:
		m.append(head2.data)
		head2 = head2.next
	if l > m:
		return 1
	elif l < m:
		return -1
	return 0


def compare(head1, head2):
	curr1 = head1
	curr2 = head2
	while curr1 != None and curr2 != None:
		if curr1.data > curr2.data:
			return 1
		if curr1.data < curr2.data:
			return -1
		curr1 = curr1.next
		curr2 = curr2.next
	return 0


def compare(head1, head2):
	(c1, c2) = (head1, head2)
	while c1 and c2:
		if c1.data > c2.data:
			return 1
		elif c1.data < c2.data:
			return -1
		(c1, c2) = (c1.next, c2.next)
	if c1 and (not c2):
		return 1
	if c2 and (not c1):
		return -1
	return 0

class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class Llist:

	def __init__(self):
		self.head = None

	def insert(self, data, tail):
		node = Node(data)
		if not self.head:
			self.head = node
			return node
		tail.next = node
		return node

def printList(head):
	while head:
		print(head.data, end=' ')
		head = head.next
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		n1 = int(input())
		arr1 = input().split()
		ll1 = Llist()
		tail = None
		for nodeData in arr1:
			tail = ll1.insert(nodeData, tail)
		n2 = int(input())
		arr2 = input().split()
		ll2 = Llist()
		tail = None
		for nodeData in arr2:
			tail = ll2.insert(nodeData, tail)
		print(compare(ll1.head, ll2.head))


def compare(head1, head2):
	(s1, s2) = ('', '')
	temp1 = head1
	temp2 = head2
	while temp1 and temp2:
		s1 += str(temp1.data)
		s2 += str(temp2.data)
		temp1 = temp1.next
		temp2 = temp2.next
	if s1 == s2:
		return 0
	if s1 > s2:
		return 1
	else:
		return -1

class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

class Llist:

	def __init__(self):
		self.head = None

	def insert(self, data, tail):
		node = Node(data)
		if not self.head:
			self.head = node
			return node
		tail.next = node
		return node

def printList(head):
	while head:
		print(head.data, end=' ')
		head = head.next
if __name__ == '__main__':
	t = int(input())
	for tcs in range(t):
		n1 = int(input())
		arr1 = input().split()
		ll1 = Llist()
		tail = None
		for nodeData in arr1:
			tail = ll1.insert(nodeData, tail)
		n2 = int(input())
		arr2 = input().split()
		ll2 = Llist()
		tail = None
		for nodeData in arr2:
			tail = ll2.insert(nodeData, tail)
		print(compare(ll1.head, ll2.head))