Find Merge Point of Two Lists| Linked List
TASK(medium)
Given pointers to the head nodes of 2 linked lists that merge together at some point, find the node where the two lists merge. The merge point is where both lists point to the same node, i.e. they reference the same memory location. It is guaranteed that the two head nodes will be different, and neither will be NULL. If the lists share a common node, return that node's data value.
Note: After the merge point, both lists will share the same node pointers.
Example
In the diagram below, the two lists converge at Node x:
[List #1] a--->b--->c
\
x--->y--->z--->NULL
/
[List #2] p--->q
Function Description
Complete the findMergeNode function in the editor below.
findMergeNode has the following parameters:
- SinglyLinkedListNode pointer head1: a reference to the head of the first list
- SinglyLinkedListNode pointer head2: a reference to the head of the second list
Returns
- int: the data value of the node where the lists merge
Input Format
The first line contains an integer, the number of test cases.
Each of the test cases is in the following format:
The first line contains an integer, the node number where the merge will occur.
The next line contains an integer, that is the number of nodes in the first list.
Each of the following lines contains a value for a node. The next line contains an integer, that is the number of nodes in the second list.
Each of the following lines contains a value for a node.
Sample Input
The diagrams below are graphical representations of the lists that input nodes and are connected to.
Test Case 0
1
\
2--->3--->NULL
/
1
Test Case 1
1--->2
\
3--->Null
/
1
Sample Output
2
3
SOLUTION 1
def findMergeNode(h1, h2):
p1, p2 = h1, h2
while p1 != p2:
p1 = p1.next if p1 else h2
p2 = p2.next if p2 else h1
return p1.data if p1 else None
EXPLANATION STEPS
1.Determine Lengths: Compute lengths of both linked lists.
2.Align Pointers: Move the pointer of the longer list ahead by the length difference.
3.Traverse and Compare: Traverse both lists simultaneously and find the first matching node.
4.Return Result: Return the merge point node or ‘null’ if no merge point exists.
