WhatsApp OA questions and answers

#include <iostream>
using namespace std;
// question 1: create a new datatype for a singly linked list
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    // question 2: write a function that merges two sorted linked lists.
    ListNode *merge(ListNode *runner1, ListNode *runner2) {
        ListNode *pre = new ListNode(0);
        ListNode *runner = pre;
        while (runner1 || runner2) {
            if (!runner2) {
                runner->next = runner1;
                runner1 = runner1->next;
            }
            else if (!runner1) {
                runner->next = runner2;
                runner2 = runner2->next;
            }
            else if (runner1->val < runner2->val) {
                runner->next = runner1;
                runner1 = runner1->next;
            }
            else {
                runner->next = runner2;
                runner2 = runner2->next;
            }
            runner = runner->next;
        }
        return pre->next;
    }

    // question 3: full merge-sort algorithm
    ListNode* mergeSort(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode *slow_runner = head, *fast_runner = head;
        while (fast_runner->next && fast_runner->next->next) {
            slow_runner = slow_runner->next;
            fast_runner = fast_runner->next->next;
        }
        ListNode *head1 = head, *head2 = slow_runner->next;
        slow_runner->next = NULL;
        return merge(mergeSort(head1), mergeSort(head2));
    }

    // to judge if my answer and expected answer is the same
    bool isEqual(ListNode *myAnswer, ListNode *expectedAnswer) {
        if (!myAnswer && !expectedAnswer)
            return true;
        if (!myAnswer || !expectedAnswer)
            return false;
        while (myAnswer && expectedAnswer) {
            if (myAnswer->val != expectedAnswer->val)
                return false;
            myAnswer = myAnswer->next;
            expectedAnswer = expectedAnswer->next;
        }
        if (myAnswer || expectedAnswer)
            return false;
        return true;
    }

    // print out the linked list
    void printList(ListNode *list) {
        if (!list) {
            cout << "NULL" << endl;
            return;
        }
        while (list) {
            cout << list->val << " ";
            list = list->next;
        }
        cout << endl;
    }
};
int main() {
    // question 4: create test cases
    Solution sol;
    ListNode *myAnswer = NULL, *correctAnswer = NULL;

    cout << "Test case 1: " << endl;;
    ListNode *tc1_1 = new ListNode(1); ListNode *tc1_2 = new ListNode(3); ListNode *tc1_3 = new ListNode(2);
    tc1_1->next = tc1_2; tc1_2->next = tc1_3;
    cout << "Input: ";
    sol.printList(tc1_1);
    ListNode *sorted_tc1_1 = new ListNode(1); ListNode *sorted_tc1_2 = new ListNode(2); ListNode *so

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

->next = tc8_2; tc8_2->next = tc8_3;
    cout << "Input: ";
    sol.printList(tc8_1);
    ListNode *sorted_tc8_1 = new ListNode(1); ListNode *sorted_tc8_2 = new ListNode(2); ListNode *sorted_tc8_3 = new ListNode(3);
    sorted_tc8_1->next = sorted_tc8_2; sorted_tc8_2->next = sorted_tc8_3;
    myAnswer = sol.mergeSort(tc8_1);
    correctAnswer = sorted_tc8_1;
    cout << "My answer: ";
    sol.printList(myAnswer);
    cout << "Expected answer: ";
    sol.printList(correctAnswer);
    if (sol.isEqual(myAnswer, correctAnswer))
        cout << "PASS!" << endl;
    else
        cout << "FAIL!" << endl;
    cout << endl;

    cout << "Test case 9: " << endl;;
    ListNode *tc9_1 = new ListNode(1); ListNode *tc9_2 = new ListNode(1); ListNode *tc9_3 = new ListNode(1);
    tc9_1->next = tc9_2; tc9_2->next = tc9_3;
    cout << "Input: ";
    sol.printList(tc9_1);
    ListNode *sorted_tc9_1 = new ListNode(1); ListNode *sorted_tc9_2 = new ListNode(1); ListNode *sorted_tc9_3 = new ListNode(1);
    sorted_tc9_1->next = sorted_tc9_2; sorted_tc9_2->next = sorted_tc9_3;
    myAnswer = sol.mergeSort(tc9_1);
    correctAnswer = sorted_tc9_1;
    cout << "My answer: ";
    sol.printList(myAnswer);
    cout << "Expected answer: ";
    sol.printList(correctAnswer);
    if (sol.isEqual(myAnswer, correctAnswer))
        cout << "PASS!" << endl;
    else
        cout << "FAIL!" << endl;
    cout << endl;
    return 0;
}