Sort a Linked List Using Merge Sort in DSA C - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to find the middle node of the linked list.

DSA C

struct Node* findMiddle(struct Node* head) {
    struct Node* slow = head;
    struct Node* fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->[1];
        fast = fast->next->next;
    }
    return slow;
}

Drag options to blanks, or click blank then click option'

Achild

Bprev

Cnext

Drandom

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' instead of 'next' for moving forward.

Using 'fast' pointer instead of 'slow' for single steps.

The slow pointer moves one step at a time using the 'next' pointer to find the middle node.

2fill in blank

medium

Complete the code to merge two sorted linked lists.

DSA C

struct Node* merge(struct Node* a, struct Node* b) {
    if (a == NULL) return b;
    if (b == NULL) return a;
    struct Node* result;
    if (a->data <= b->data) {
        result = a;
        result->next = merge(a->next, [1]);
    } else {
        result = b;
        result->next = merge(a, b->next);
    }
    return result;
}

Drag options to blanks, or click blank then click option'

Aa

Bb

Cresult

DNULL

Attempts:

3 left

💡 Hint

Common Mistakes

Passing 'a' instead of 'b' in the recursive call.

Passing NULL instead of the other list.

When a's data is smaller, we merge the rest of a's list with b starting from b.

3fill in blank

hard

Fix the error in the mergeSort function to correctly split the list.

DSA C

struct Node* mergeSort(struct Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct Node* middle = findMiddle(head);
    struct Node* nextOfMiddle = middle->[1];
    middle->next = NULL;
    struct Node* left = mergeSort(head);
    struct Node* right = mergeSort(nextOfMiddle);
    struct Node* sortedList = merge(left, right);
    return sortedList;
}

Drag options to blanks, or click blank then click option'

Arandom

Bprev

Cchild

Dnext

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'prev' instead of 'next' to get the next node.

Not setting middle->next to NULL to split the list.

To split the list, we get the node after middle using 'next'.

4fill in blank

hard

Fill both blanks to complete the merge function's base cases.

DSA C

struct Node* merge(struct Node* a, struct Node* b) {
    if (a == [1]) return b;
    if (b == [2]) return a;
    // rest of merge code
}

Drag options to blanks, or click blank then click option'

ANULL

B0

Chead

Dfalse

Attempts:

3 left

💡 Hint

Common Mistakes

Using 0 or false instead of NULL for pointers.

Checking against 'head' which is undefined here.

When either list is empty (NULL), return the other list.

5fill in blank

hard

Fill all three blanks to complete the mergeSort function call and return.

DSA C

struct Node* mergeSort(struct Node* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    struct Node* middle = findMiddle(head);
    struct Node* nextOfMiddle = middle->next;
    middle->next = NULL;
    struct Node* left = mergeSort([1]);
    struct Node* right = mergeSort([2]);
    struct Node* sortedList = merge([3], right);
    return sortedList;
}

Drag options to blanks, or click blank then click option'

Ahead

BnextOfMiddle

Cleft

Dmiddle

Attempts:

3 left

💡 Hint

Common Mistakes

Passing middle instead of nextOfMiddle for right half.

Merging unsorted lists instead of sorted ones.

Recursively sort left half (head), right half (nextOfMiddle), then merge left and right.