Write a function to find the node where two linked lists meet.

Question

Dan · Accepted Answer

// solution in C++ #include #include 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 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 val next; } cout val next; } cout << endl;

Dan · Answer

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 val next;
    }
    cout val next;
    }
    cout val << endl;

    cout << "

Press Enter to quit. ";
    cin.ignore();
    return 0;
}

Tama · Answer

public static void main(String[] args) {
        List L1 = Arrays.asList(1,2,5,7,9,10,12,18,3);
        List L2 = Arrays.asList(2,3,4,8,9,9,10,11,12,18);

        LinkedList list1 = new LinkedList();
        list1.addAll(L1);
        LinkedList list2 = new LinkedList();
        list2.addAll(L2);

        System.out.println("L1      : " + list1);
        System.out.println("L2      : " + list2);
    	ArrayList result = new ArrayList();
        System.out.println("two linked lists meet: " + findCommon(list1, list2,result));
    }
    public static ArrayList findCommon(LinkedList list1,LinkedList list2,ArrayList result)
    {
        if (list1.isEmpty()) return result;
        int pop = list1.pop();
        if (list2.contains(pop))  result.add(pop);
        return findCommon(list1, list2, result);
    }

Amazon

Pergunta de entrevista da empresa Amazon

Respostas da entrevista

Empresas seguidas

Buscas de vagas