Find the Intersection Node of Two Linked Lists

You are given two singly linked lists that may or may not intersect. Two linked lists intersect if they share some common nodes by reference (not just by value). Your task is to find the node at which the two linked lists intersect and output its value. If they do not intersect, output 0.

The intersection is defined in the following way. Suppose the first list has n nodes and the second list has m nodes. Additionally, an integer k is provided. If k >= 0, the node at index k (0-indexed) in the first list becomes the starting point of a common tail which is shared with the second list by linking the tail of the second list (its unique part) to that node. If k = -1, there is no intersection between the two lists.

Your goal is to determine the intersection node by reading the lists from standard input, and print the value stored in that node. If there is no intersection, print 0 instead.

The solution must use an algorithm, for example, by computing the lengths of both lists and adjusting the starting pointers so that they align and can then be traversed in tandem.

Note: When referring to any formulas, use \(\LaTeX\) format for the mathematical expressions.

inputFormat

The input is provided via standard input (stdin) and is formatted as follows:

n m k
v1 v2 ... vn
w1 w2 ... wm

• n: the number of nodes in the first linked list.
• m: the number of nodes in the unique part of the second linked list.
• k: an integer representing the 0-indexed position in the first list where the intersection starts. If k = -1, then there is no intersection.
• The next line contains n integers representing the values of the nodes in the first list.
• The following line contains m integers representing the values of the nodes in the second list (before the intersection, if any).

If an intersection exists (k != -1), then the tail of the second list is linked to the k-th node of the first list, thereby sharing all subsequent nodes.

outputFormat

Output a single integer to standard output (stdout) which is the value of the intersection node. If the lists do not intersect, output 0.

## sample

3 3 -1
1 2 3
4 5 6

0