Last Updated: 29 Sep, 2020
Match Number
Easy
Asked in companies
Given two linked lists, check whether they represent the same number. Each node of the list represents part of the whole integer which needs to be matched. Return True if the lists match, otherwise return False.
Input Format:
The first line of the input contains an integer 'T' denoting the number of test cases.
The next '2T' line contains some integers each line denotes one linked list.
Elements of the linked list are separated by space. A linked list is terminated by -1.
Output Format:
For each test case, print True if the given lists match, else print False.
Note:
You do not need to print anything, it has already been taken care of. Just implement the function and return the answer.
Constraints:
1 <= T <= 10
1 <= N1 <= 10^4
1 <= N2 <= 10^4
Where N1, N2 represents the length of linked list one and two respectively.
Time Limit: 1 sec
Approaches
- Maintain two empty strings at the start for each linked list.
- Now recursively go through each element of the first linked list and convert its elements into char representation.
- Simultaneously add those char to the string of linked list-1.
- Repeat the same process for the second linked list.
- We also need to eliminate appending zeros as ‘01’ and ‘1’ represent the same number.
- Hence we skip adding those elements for which element data is 0 and the size of the string is 0 because that would denote appended zeros.
- We get two strings, each of which denotes a combined number formed by elements of the linked list.
- Compare those two strings and return true if they match, else return false.