Combining two sorted lists involves iteratively comparing nodes and linking the smaller value to the result list. The process resembles a zipper mehcanism or enzymatic assembly. A dummy head node simplifies edge-case handling.

#include <stdlib.h>
struct Node {
    int data;
    struct Node* link;
};

struct Node* combineSorted(struct Node* first, struct Node* second) {
    struct Node sentinel;
    sentinel.link = NULL;
    struct Node* current = &sentinel;
    while (first && second) {
        if (first->data < second->data) {
            current->link = first;
            first = first->link;
        } else {
            current->link = second;
            second = second->link;
        }
        current = current->link;
    }
    current->link = first ? first : second;
    return sentinel.link;
}

Separating a Single List

To split a list around a pivot x, create two sublists for elements less than x and those greater or equal. Append the second sublist after the first.

struct Node* separateList(struct Node* head, int x) {
    struct Node left_dummy, right_dummy;
    left_dummy.link = right_dummy.link = NULL;
    struct Node *left = &left_dummy, *right = &right_dummy;
    struct Node* cursor = head;
    while (cursor) {
        if (cursor->data < x) {
            left->link = cursor;
            left = left->link;
        } else {
            right->link = cursor;
            right = right->link;
        }
        struct Node* next_node = cursor->link;
        cursor->link = NULL;
        cursor = next_node;
    }
    left->link = right_dummy.link;
    return left_dummy.link;
}

Merging Multiple Sorted Lists

For k sorted lists, a min-heap efficiently retrieves the smallest node. Each node insertion and removal costs O(log k), leading to O(N log k) total time.

#include <stdio.h>
#include <stdlib.h>
struct Node {
    int value;
    struct Node* next;
};
struct HeapNode {
    struct Node* list_node;
};

void heapifyDown(struct HeapNode heap[], int heap_size, int idx) {
    int smallest = idx;
    int left = 2 * idx + 1;
    int right = 2 * idx + 2;
    if (left < heap_size && heap[left].list_node->value < heap[smallest].list_node->value) {
        smallest = left;
    }
    if (right < heap_size && heap[right].list_node->value < heap[smallest].list_node->value) {
        smallest = right;
    }
    if (smallest != idx) {
        struct HeapNode temp = heap[idx];
        heap[idx] = heap[smallest];
        heap[smallest] = temp;
        heapifyDown(heap, heap_size, smallest);
    }
}

struct Node* mergeKSorted(struct Node* lists[], int k) {
    struct HeapNode* heap = (struct HeapNode*)malloc(k * sizeof(struct HeapNode));
    int heap_size = 0;
    for (int i = 0; i < k; i++) {
        if (lists[i]) {
            heap[heap_size++].list_node = lists[i];
        }
    }
    for (int i = (heap_size - 1) / 2; i >= 0; i--) {
        heapifyDown(heap, heap_size, i);
    }
    struct Node dummy_head;
    dummy_head.next = NULL;
    struct Node* tail = &dummy_head;
    while (heap_size > 0) {
        struct Node* min_node = heap[0].list_node;
        tail->next = min_node;
        tail = tail->next;
        if (min_node->next) {
            heap[0].list_node = min_node->next;
        } else {
            heap[0] = heap[--heap_size];
        }
        if (heap_size > 0) {
            heapifyDown(heap, heap_size, 0);
        }
    }
    free(heap);
    return dummy_head.next;
}

Finding the K-th Node from End

Use two pointers. Advance the first k steps, then move both simultaneously. When the first reaches the end, the second points to the target node.

struct Node* kthFromEnd(struct Node* head, int k) {
    struct Node* lead = head;
    for (int i = 0; i < k; i++) {
        lead = lead->link;
    }
    struct Node* follow = head;
    while (lead) {
        lead = lead->link;
        follow = follow->link;
    }
    return follow;
}

Deleting the K-th Node from End

Find the (k+1)-th node from the end using the same technique and adjust its next pointer. A sentinel node handles cases where the head needs deletion.

struct Node* deleteKthFromEnd(struct Node* head, int n) {
    struct Node sentinel;
    sentinel.link = head;
    struct Node* target_prev = kthFromEnd(&sentinel, n + 1);
    target_prev->link = target_prev->link->link;
    return sentinel.link;
}

Locating the Middle Node

Initialize slow and fast pointers at the head. Move slow by one step and fast by two. When fast reaches the end, slow is at the middle.

struct Node* findMiddle(struct Node* head) {
    struct Node* slow = head;
    struct Node* fast = head;
    while (fast && fast->link) {
        slow = slow->link;
        fast = fast->link->link;
    }
    return slow;
}

Detecting a Cycle

If a cycle exists, the fast pointer will eventually meet the slow pointer.

#include <stdbool.h>
bool hasCycle(struct Node* head) {
    struct Node* slow = head;
    struct Node* fast = head;
    while (fast && fast->link) {
        slow = slow->link;
        fast = fast->link->link;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

Finding the Start of a Cycle

After detecting a cycle, reset one pointer to the head. Advance both at the same speed; the meeting point is the cycle's start.

struct Node* cycleStart(struct Node* head) {
    struct Node* slow = head;
    struct Node* fast = head;
    while (fast && fast->link) {
        slow = slow->link;
        fast = fast->link->link;
        if (slow == fast) break;
    }
    if (!fast || !fast->link) return NULL;
    slow = head;
    while (slow != fast) {
        slow = slow->link;
        fast = fast->link;
    }
    return slow;
}

Intersection of Two Lists

Traverse both lists. When a pointer reaches the end of its list, redirect it to the head of the other list. The meeting point is the intersection.

struct Node* findIntersection(struct Node* headA, struct Node* headB) {
    struct Node* ptrA = headA;
    struct Node* ptrB = headB;
    while (ptrA != ptrB) {
        ptrA = ptrA ? ptrA->link : headB;
        ptrB = ptrB ? ptrB->link : headA;
    }
    return ptrA;
}