合并两个有序链表

在处理链表数据时，将两个已经按升序排列的链表合并为一个新的升序链表是经典操作。我们可以通过归并排序的思想，依次比较两个链表的头节点，将较小的节点接入新链表的末尾。

#include <iostream>
#include <vector>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* mergeSortedLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0);
    ListNode* tail = &dummy;

    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    
    // 连接剩余部分
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

int main() {
    int n, m;
    if (!(std::cin >> n >> m)) return 0;
    
    auto createList = [](int count) {
        ListNode dummy(0);
        ListNode* curr = &dummy;
        for (int i = 0; i < count; ++i) {
            int val;
            std::cin >> val;
            curr->next = new ListNode(val);
            curr = curr->next;
        }
        return dummy.next;
    };

    ListNode* head1 = createList(n);
    ListNode* head2 = createList(m);
    ListNode* result = mergeSortedLists(head1, head2);

    while (result) {
        std::cout << result->val << " ";
        result = result->next;
    }
    return 0;
}

利用快慢指针寻找中间节点

对于长度为 $n$（且 $n$ 为偶数）的链表，寻找第 $n/2$ 个元素可以使用"快慢指针"算法。快指针每次移动两步，慢指针每次移动一步。当快指针到达链表末尾附近时，慢指针恰好指向目标位置。

#include <iostream>

struct Node {
    int data;
    Node* next;
};

void findMiddle(int n) {
    Node* head = nullptr;
    Node* tail = nullptr;

    for (int i = 0; i < n; ++i) {
        int val;
        std::cin >> val;
        Node* newNode = new Node{val, nullptr};
        if (!head) head = tail = newNode;
        else {
            tail->next = newNode;
            tail = newNode;
        }
    }

    Node *slow = head, *fast = head;
    // 针对n为偶数，寻找第n/2个节点
    // 逻辑：fast先走一步，随后fast走两步slow走一步
    if (fast) fast = fast->next;
    while (fast && fast->next && fast->next->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    std::cout << slow->data << std::endl;
}

int main() {
    int n;
    if (std::cin >> n) findMiddle(n);
    return 0;
}

单链表的原地翻转

要实现链表的逆序输出，最有效率的方法是原地翻转链表的指针方向。我们需要维护三个指针：当前节点（curr）、前驱节点（prev）以及后继节点（nextTemp），以确保在断开当前连接时不会丢失后续链表的信息。

#include <iostream>

struct Node {
    int score;
    Node* next;
};

Node* reverseList(Node* head) {
    Node* prev = nullptr;
    Node* curr = head;
    while (curr) {
        Node* nextTemp = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextTemp;
    }
    return prev;
}

int main() {
    int n;
    std::cin >> n;
    Node* head = nullptr;
    Node* tail = nullptr;
    for (int i = 0; i < n; ++i) {
        int s;
        std::cin >> s;
        Node* node = new Node{s, nullptr};
        if (!head) head = tail = node;
        else {
            tail->next = node;
            tail = node;
        }
    }

    Node* newHead = reverseList(head);
    while (newHead) {
        std::cout << newHead->score << "\n";
        newHead = newHead->next;
    }
    return 0;
}

双向链表的局部区间翻转

双向链表通过 prev 和 next 指针记录前后元素。在处理区间翻转时，除了要像单链表一样翻转内部指针，还需要特别处理区间边界与原链表剩余部分的连接关系。

#include <iostream>
#include <vector>

struct DoubleNode {
    int id;
    DoubleNode *prev, *next;
    DoubleNode(int v) : id(v), prev(nullptr), next(nullptr) {}
};

int main() {
    int n, m;
    std::cin >> n >> m;

    std::vector<DoubleNode*> nodes(n + 1);
    DoubleNode* head = nullptr;
    DoubleNode* tail = nullptr;

    for (int i = 1; i <= n; ++i) {
        nodes[i] = new DoubleNode(i);
        if (!head) head = tail = nodes[i];
        else {
            tail->next = nodes[i];
            nodes[i]->prev = tail;
            tail = nodes[i];
        }
    }

    while (m--) {
        int l, r;
        std::cin >> l >> r;
        if (l >= r) continue;

        DoubleNode *nodeL = head, *nodeR = head;
        for (int i = 1; i < l; ++i) nodeL = nodeL->next;
        for (int i = 1; i < r; ++i) nodeR = nodeR->next;

        DoubleNode *before = nodeL->prev;
        DoubleNode *after = nodeR->next;

        // 翻转区间 [nodeL, nodeR]
        DoubleNode *curr = nodeL;
        while (curr != after) {
            DoubleNode *temp = curr->next;
            curr->next = curr->prev;
            curr->prev = temp;
            curr = temp;
        }

        // 处理边界连接
        if (before) {
            before->next = nodeR;
            nodeR->prev = before;
        } else {
            head = nodeR;
            nodeR->prev = nullptr;
        }

        if (after) {
            after->prev = nodeL;
            nodeL->next = after;
        } else {
            tail = nodeL;
            nodeL->next = nullptr;
        }
    }

    for (DoubleNode* p = head; p; p = p->next) {
        std::cout << p->id << (p->next ? " " : "");
    }
    return 0;
}

链表的特殊形态：循环链表

循环链表是将单向或双向链表的首尾相连，形成一个闭环结构。这种结构在处理具有周期性性质的问题（如约瑟夫环问题）时非常高效。在双向循环链表中，head->prev 指向 tail，而 tail->next 指向 head。