Merge Sort for Singly Linked Lists

When dealing with singly linked lists, Merge Sort is often the preferred sorting algorithm due to its O(n log n) time complexity and efficiency in sequential data structures. Unlike arrays, linked lists do not allow random access, which makes algorithms like QuickSort less efficient. The core logic relies on the divide-and-conquer strategy: recursively splitting the list into halves, sorting each half, and finally merging them back together.

The recursive process can be broken down into three main phases:

1. Base Case: If the list is empty or contains only one node, it is already sorted.
2. Partition: Locate the middle node to split the list into two distinct sub-lists. This is typically achieved using the slow and fast pointer technique. The fast pointer moves two steps while the slow pointer moves one step. When the fast pointer reaches the end, the slow pointer will be at the midpoint. Crucially, the link at the midpoint must be severed (setting mid->next = NULL) to ensure the recursive calls operate on independent segments.
3. Merge: Recursively sort the left and right halves, then merge the two sorted lists into a single sorted list.

Below is a C implementation demonstrating this approach. The merge logic is handled iteratively for efficiency, while the sorting logic remains recursive.

#include <stdlib.h>

typedef struct ListNode {
    int val;
    struct ListNode* next;
} ListNode;

// Helper function to merge two sorted lists iteratively
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy; // Dummy node to simplify edge cases
    ListNode* tail = &dummy;
    dummy.next = NULL;

    while (l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }

    // Attach the remaining elements
    tail->next = (l1 != NULL) ? l1 : l2;
    return dummy.next;
}

ListNode* sortList(ListNode* head) {
    // Base case: empty list or single node
    if (head == NULL || head->next == NULL) {
        return head;
    }

    // Find the middle using slow/fast pointers
    ListNode* slow = head;
    ListNode* fast = head->next;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }

    // Split the list
    ListNode* mid = slow->next;
    slow->next = NULL; // Terminate the first half

    // Recursive calls
    ListNode* left = sortList(head);
    ListNode* right = sortList(mid);

    // Merge the sorted halves
    return mergeTwoLists(left, right);
}

Climbing Stairs Problem

A classic algorithmic puzzle involves calculating the number of distinct ways to climb a staircase of n steps, where you can take either 1 or 2 steps at a time. This problem is a canonical example of Dynamic Programming.

To reach the n-th step, you must have arrived from either the (n-1)-th step or the (n-2)-th step. Therefore, the total number of ways to reach the n-th step is the sum of the ways to reach the previous two steps. This establishes the recurrence relation:

f(n) = f(n-1) + f(n-2)

This sequence is identical to the Fibonacci sequence. We can solve this efficiently using an iterative approach to avoid the overhead of recursion.

int climbStairs(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;

    int prev = 1; // Represents f(n-2)
    int curr = 2; // Represents f(n-1)
    int result = 0;

    for (int i = 3; i <= n; i++) {
        result = prev + curr;
        prev = curr;
        curr = result;
    }

    return curr;
}