Intersection of Two Linked Lists

You are given two singly linked lists. The lists may or may not intersect. If they do intersect, the intersection is defined by the node reference (i.e. the same node in memory) where the two lists merge. Your task is to determine the data value of the intersection node. If the lists do not intersect, output -1.

The input consists of two linked lists. For the second list, a connection can be established such that its last node points to a node in the first list. This connection is specified by an index k (0-indexed) into the first list. If k = -1, the lists do not intersect.

Your algorithm should run in linear time and use constant extra space. Formally, if n is the number of nodes in the longer list, your solution should run in \(O(n)\) time.

inputFormat

The input is read from standard input (stdin) in the following format:

 n1
 node1_1 node1_2 ... node1_n1
 n2
 node2_1 node2_2 ... node2_n2
 k

Here,

• n1 is the number of nodes in the first linked list.
• The next line contains n1 integers representing the node values of the first list.
• n2 is the number of nodes in the second linked list before merging.
• The following line contains n2 integers representing the node values of the second list.
• k is an integer representing the 0-indexed position in the first list where the tail of the second list will be connected. If k = -1, the lists do not intersect.

outputFormat

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

4
3 6 15 30
1
10
2

15