Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Linked List

Intersection of Two Linked Lists

Medium · Linked List · Asked at Amazon, Microsoft, Google, Bloomberg, Flipkart

Two lists may share a common tail (the very same nodes). List A = its own part followed by the shared part; list B = its own part followed by the shared part. Print the value of the first shared node, or -1 if there is no shared part. Values can repeat, so compare nodes, not values.

Input

First line: a b c — sizes of A's own part, B's own part and the shared part. The next three lines hold those values (a line is empty when its size is 0).

Output

The value of the intersection node, or -1.

Constraints

Walk pointer pA through A then B, and pB through B then A. Both cover a + b + c nodes before reaching the shared part, so they meet at the intersection (or both reach null).

Example 1

Input

2 3 3
4 1
5 6 1
8 4 5

Output

8

Example 2

Input

3 2 0
2 6 4
1 5

Output

-1

Hints

  1. Equal values do not mean the same node — compare node references.
  2. Pointer pA walks A and then B; pointer pB walks B and then A. They travel the same total distance, so they reach the shared node together (or null together).

Approach

Build the shared nodes once and attach them to the ends of both own parts. Then run the two-pointer trick: each pointer, on reaching the end of its list, jumps to the head of the other list. After at most a + b + c steps both have walked a + b nodes before the shared part, so they arrive at its first node at the same time; with no shared part they both become null.

Complexity: O(a + b + c) time · O(1) extra space

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

struct Node {
    long long val;
    Node *next = nullptr;
    Node(long long v) : val(v) {}
};

// reads k values and returns {head, tail}
pair<Node *, Node *> readPart(int k) {
    Node dummy(0), *t = &dummy;
    for (int i = 0; i < k; i++) {
        long long x;
        cin >> x;
        t = t->next = new Node(x);
    }
    return {dummy.next, k ? t : nullptr};
}

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    auto A = readPart(a), B = readPart(b), C = readPart(c);
    Node *headA = A.first ? A.first : C.first, *headB = B.first ? B.first : C.first;
    if (A.second) A.second->next = C.first;
    if (B.second) B.second->next = C.first;
    Node *p = headA, *q = headB;
    while (p != q) {
        p = p ? p->next : headB;
        q = q ? q->next : headA;
    }
    cout << (p ? p->val : -1) << "\n";
    return 0;
}

Python solution

import sys


class Node:
    def __init__(self, val):
        self.val, self.next = val, None


def build(vals):
    dummy = tail = Node(0)
    for v in vals:
        tail.next = Node(v)
        tail = tail.next
    return dummy.next, (tail if vals else None)


data = list(map(int, sys.stdin.read().split()))
a, b, c = data[0], data[1], data[2]
vals = data[3:]
ha, ta = build(vals[:a])
hb, tb = build(vals[a : a + b])
hc, _ = build(vals[a + b : a + b + c])
if ta:
    ta.next = hc
if tb:
    tb.next = hc
head_a, head_b = ha or hc, hb or hc
p, q = head_a, head_b
while p is not q:
    p = p.next if p else head_b
    q = q.next if q else head_a
print(p.val if p else -1)

Java solution

import java.util.*;

public class Main {
    static class Node {
        long val;
        Node next;
        Node(long v) { val = v; }
    }

    static Node[] readPart(Scanner sc, int k) {
        Node dummy = new Node(0), t = dummy;
        for (int i = 0; i < k; i++) t = t.next = new Node(sc.nextLong());
        return new Node[] {dummy.next, k > 0 ? t : null};
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
        Node[] A = readPart(sc, a), B = readPart(sc, b), C = readPart(sc, c);
        if (A[1] != null) A[1].next = C[0];
        if (B[1] != null) B[1].next = C[0];
        Node headA = A[0] != null ? A[0] : C[0], headB = B[0] != null ? B[0] : C[0];
        Node p = headA, q = headB;
        while (p != q) {
            p = p != null ? p.next : headB;
            q = q != null ? q.next : headA;
        }
        System.out.println(p != null ? p.val : -1);
    }
}

Solve Intersection of Two Linked Lists online · All practice problems