Amazon.com

www.amazon.com
Employer Engaged

Interview Question

Software Design Engineer In Test Interview Seattle, WA

Write a function to find the node where two linked lists

  meet.
Answer

Interview Answer

3 Answers

0

public static void main(String[] args) {
        List<Integer> L1 = Arrays.asList(1,2,5,7,9,10,12,18,3);
        List<Integer> L2 = Arrays.asList(2,3,4,8,9,9,10,11,12,18);

        LinkedList<Integer> list1 = new LinkedList<Integer>();
        list1.addAll(L1);
        LinkedList<Integer> list2 = new LinkedList<Integer>();
        list2.addAll(L2);

        System.out.println("L1 : " + list1);
        System.out.println("L2 : " + list2);
        ArrayList<Integer> result = new ArrayList<Integer>();
        System.out.println("two linked lists meet: " + findCommon(list1, list2,result));
    }
    public static ArrayList<Integer> findCommon(LinkedList<Integer> list1,LinkedList<Integer> list2,ArrayList<Integer> result)
    {
        if (list1.isEmpty()) return result;
        int pop = list1.pop();
        if (list2.contains(pop)) result.add(pop);
        return findCommon(list1, list2, result);
    }

Tama on Nov 28, 2010
0

// solution in C++
#include <iostream>
#include <map>

using namespace std;

// simple Node class
class Node
{
public:
    Node(int v) : val(v), next(NULL) {}
    int val;
    Node* next;
};

// function to find intersection Node
Node* findNodeWhere2ListsMeet(Node* head1, Node* head2)
{
    // interate through first list and populate map
    map<Node*, int> nodeMap;
    while (head1 != NULL)
    {
        nodeMap[head1] = head1->val;
        head1 = head1->next;
    }
    // interate through second list and try to find in map
    while (head2 != NULL)
    {
        if (nodeMap.find(head2) != nodeMap.end())
        {
            return head2;
        }
        head2 = head2->next;
    }
    return NULL;
}

// test code (happy path only)
int main()
{
    // linked list 1 values = 1,2,3,4,5,6
    Node* head1 = new Node(1);
    Node* n12 = new Node(2);
    Node* n13 = new Node(3);
    Node* n14 = new Node(4);
    Node* n15 = new Node(5);
    Node* n16 = new Node(6);
    head1->next = n12;
    n12->next = n13;
    n13->next = n14;
    n14->next = n15;
    n15->next = n16;

    // linked list 2 values = 11,12,13,5,6
    Node* head2 = new Node(11);
    Node* n22 = new Node(12);
    Node* n23 = new Node(13);
    head2->next = n22;
    n22->next = n23;
    n23->next = n15;

    Node* intersection = findNodeWhere2ListsMeet(head1, head2);

    while (head1 != NULL)
    {
        cout << head1->val << " ";
        head1 = head1->next;
    }
    cout << endl;

    while (head2 != NULL)
    {
        cout << head2->val << " ";
        head2 = head2->next;
    }
    cout << endl;

Dan on Sep 26, 2011
0

Previous answer got truncated. Here's the last of the test code starting at the function call.

    Node* intersection = findNodeWhere2ListsMeet(head1, head2);

    while (head1 != NULL)
    {
        cout << head1->val << " ";
        head1 = head1->next;
    }
    cout << endl;

    while (head2 != NULL)
    {
        cout << head2->val << " ";
        head2 = head2->next;
    }
    cout << endl;

    cout << "lists intersect at " << intersection->val << endl;

    cout << "\n\n\nPress Enter to quit. ";
    cin.ignore();
    return 0;
}

Dan on Sep 26, 2011

Add Answers or Comments

To comment on this, Sign In or Sign Up.