《链表算法实战解析与双向链表实现深度剖析》

链表作为基础而重要的数据结构，在算法设计和系统开发中扮演着关键角色。理解单向链表算法和掌握双向链表实现，是提升编程能力的重要环节。

**单向链表基础实现**

```cpp

class ListNode {

public:

    int val;

    ListNode* next;

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

};

class SinglyLinkedList {

private:

    ListNode* head;

    int size;

    

public:

    SinglyLinkedList() : head(nullptr), size(0) {}

    

    ~SinglyLinkedList() {

        clear();

    }

    

    // 在头部插入节点

    void insertAtHead(int val) {

        ListNode* newNode = new ListNode(val);

        newNode->next = head;

        head = newNode;

        size++;

    }

    

    // 在尾部插入节点

    void insertAtTail(int val) {

        ListNode* newNode = new ListNode(val);

        

        if (!head) {

            head = newNode;

        } else {

            ListNode* current = head;

            while (current->next) {

                current = current->next;

            }

            current->next = newNode;

        }

        size++;

    }

    

    // 在指定位置插入节点

    bool insertAtIndex(int index, int val) {

        if (index < 0 || index > size) return false;

        

        if (index == 0) {

            insertAtHead(val);

            return true;

        }

        

        ListNode* newNode = new ListNode(val);

        ListNode* current = head;

        

        for (int i = 0; i < index - 1; i++) {

            current = current->next;

        }

        

        newNode->next = current->next;

        current->next = newNode;

        size++;

        return true;

    }

    

    // 删除指定值节点

    bool deleteNode(int val) {

        if (!head) return false;

        

        if (head->val == val) {

            ListNode* temp = head;

            head = head->next;

            delete temp;

            size--;

            return true;

        }

        

        ListNode* current = head;

        while (current->next && current->next->val != val) {

            current = current->next;

        }

        

        if (current->next) {

            ListNode* temp = current->next;

            current->next = current->next->next;

            delete temp;

            size--;

            return true;

        }

        

        return false;

    }

    

    // 查找节点

    ListNode* search(int val) {

        ListNode* current = head;

        while (current) {

            if (current->val == val) return current;

            current = current->next;

        }

        return nullptr;

    }

    

    // 获取链表长度

    int getSize() const {

        return size;

    }

    

    // 清空链表

    void clear() {

        while (head) {

            ListNode* temp = head;

            head = head->next;

            delete temp;

        }

        size = 0;

    }

    

    // 打印链表

    void print() const {

        ListNode* current = head;

        cout << "链表内容: ";

        while (current) {

            cout << current->val << " -> ";

            current = current->next;

        }

        cout << "NULL" << endl;

    }

};

```

**链表反转算法**

```cpp

class LinkedListAlgorithms {

public:

    // 迭代法反转链表

    static ListNode* reverseIterative(ListNode* head) {

        ListNode* prev = nullptr;

        ListNode* current = head;

        ListNode* next = nullptr;

        

        while (current) {

            next = current->next;  // 保存下一个节点

            current->next = prev;  // 反转指针

            prev = current;        // 移动prev

            current = next;        // 移动current

        }

        

        return prev;  // 新的头节点

    }

    

    // 递归法反转链表

    static ListNode* reverseRecursive(ListNode* head) {

        if (!head || !head->next) return head;

        

        ListNode* newHead = reverseRecursive(head->next);

        head->next->next = head;

        head->next = nullptr;

        

        return newHead;

    }

    

    // 反转链表的一部分

    static ListNode* reverseBetween(ListNode* head, int left, int right) {

        if (!head || left == right) return head;

        

        ListNode* dummy = new ListNode(0);

        dummy->next = head;

        ListNode* pre = dummy;

        

        // 移动到left的前一个节点

        for (int i = 1; i < left; i++) {

            pre = pre->next;

        }

        

        // 开始反转

        ListNode* current = pre->next;

        ListNode* next = nullptr;

        

        for (int i = left; i < right; i++) {

            next = current->next;

            current->next = next->next;

            next->next = pre->next;

            pre->next = next;

        }

        

        ListNode* result = dummy->next;

        delete dummy;

        return result;

    }

};

```

**快慢指针算法**

```cpp

class FastSlowPointer {

public:

    // 检测链表是否有环

    static bool hasCycle(ListNode* head) {

        if (!head || !head->next) return false;

        

        ListNode* slow = head;

        ListNode* fast = head;

        

        while (fast && fast->next) {

            slow = slow->next;

            fast = fast->next->next;

            

            if (slow == fast) return true;

        }

        

        return false;

    }

    

    // 找到环的入口节点

    static ListNode* detectCycle(ListNode* head) {

        if (!head || !head->next) return nullptr;

        

        ListNode* slow = head;

        ListNode* fast = head;

        bool hasCycle = false;

        

        // 第一阶段：检测是否有环

        while (fast && fast->next) {

            slow = slow->next;

            fast = fast->next->next;

            

            if (slow == fast) {

                hasCycle = true;

                break;

            }

        }

        

        if (!hasCycle) return nullptr;

        

        // 第二阶段：找到环的入口

        slow = head;

        while (slow != fast) {

            slow = slow->next;

            fast = fast->next;

        }

        

        return slow;

    }

    

    // 找到链表中点

    static ListNode* findMiddle(ListNode* head) {

        if (!head) return nullptr;

        

        ListNode* slow = head;

        ListNode* fast = head;

        

        while (fast && fast->next) {

            slow = slow->next;

            fast = fast->next->next;

        }

        

        return slow;

    }

    

    // 判断链表是否回文

    static bool isPalindrome(ListNode* head) {

        if (!head || !head->next) return true;

        

        // 找到中点

        ListNode* slow = head;

        ListNode* fast = head;

        

        while (fast && fast->next) {

            slow = slow->next;

            fast = fast->next->next;

        }

        

        // 反转后半部分

        ListNode* secondHalf = reverseIterative(slow);

        ListNode* firstHalf = head;

        ListNode* secondHalfCopy = secondHalf;

        

        // 比较两半是否相同

        bool result = true;

        while (secondHalf) {

            if (firstHalf->val != secondHalf->val) {

                result = false;

                break;

            }

            firstHalf = firstHalf->next;

            secondHalf = secondHalf->next;

        }

        

        // 恢复原链表

        reverseIterative(secondHalfCopy);

        

        return result;

    }

};

```

**合并有序链表**

```cpp

class MergeLists {

public:

    // 合并两个有序链表

    static ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

        ListNode* dummy = new ListNode(0);

        ListNode* current = dummy;

        

        while (l1 && l2) {

            if (l1->val < l2->val) {

                current->next = l1;

                l1 = l1->next;

            } else {

                current->next = l2;

                l2 = l2->next;

            }

            current = current->next;

        }

        

        // 连接剩余部分

        if (l1) current->next = l1;

        if (l2) current->next = l2;

        

        ListNode* result = dummy->next;

        delete dummy;

        return result;

    }

    

    // 合并K个有序链表

    static ListNode* mergeKLists(vector<ListNode*>& lists) {

        if (lists.empty()) return nullptr;

        

        // 使用优先队列（最小堆）

        auto cmp = [](ListNode* a, ListNode* b) {

            return a->val > b->val;

        };

        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);

        

        // 将每个链表的头节点加入堆

        for (ListNode* list : lists) {

            if (list) pq.push(list);

        }

        

        ListNode* dummy = new ListNode(0);

        ListNode* current = dummy;

        

        while (!pq.empty()) {

            ListNode* node = pq.top();

            pq.pop();

            

            current->next = node;

            current = current->next;

            

            if (node->next) {

                pq.push(node->next);

            }

        }

        

        ListNode* result = dummy->next;

        delete dummy;

        return result;

    }

    

    // 两数相加（链表表示的数字）

    static ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        ListNode* dummy = new ListNode(0);

        ListNode* current = dummy;

        int carry = 0;

        

        while (l1 || l2 || carry) {

            int sum = carry;

            

            if (l1) {

                sum += l1->val;

                l1 = l1->next;

            }

            

            if (l2) {

                sum += l2->val;

                l2 = l2->next;

            }

            

            carry = sum / 10;

            current->next = new ListNode(sum % 10);

            current = current->next;

        }

        

        ListNode* result = dummy->next;

        delete dummy;

        return result;

    }

};

```

**双向链表完整实现**

```cpp

class DoublyListNode {

public:

    int val;

    DoublyListNode* prev;

    DoublyListNode* next;

    

    DoublyListNode(int x) : val(x), prev(nullptr), next(nullptr) {}

    DoublyListNode(int x, DoublyListNode* p, DoublyListNode* n) 

        : val(x), prev(p), next(n) {}

};

class DoublyLinkedList {

private:

    DoublyListNode* head;

    DoublyListNode* tail;

    int size;

    

public:

    DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}

    

    ~DoublyLinkedList() {

        clear();

    }

    

    // 在头部插入节点

    void insertAtHead(int val) {

        DoublyListNode* newNode = new DoublyListNode(val);

        

        if (!head) {

            head = tail = newNode;

        } else {

            newNode->next = head;

            head->prev = newNode;

            head = newNode;

        }

        size++;

    }

    

    // 在尾部插入节点

    void insertAtTail(int val) {

        DoublyListNode* newNode = new DoublyListNode(val);

        

        if (!tail) {

            head = tail = newNode;

        } else {

            newNode->prev = tail;

            tail->next = newNode;

            tail = newNode;

        }

        size++;

    }

    

    // 在指定位置插入节点

    bool insertAtIndex(int index, int val) {

        if (index < 0 || index > size) return false;

        

        if (index == 0) {

            insertAtHead(val);

            return true;

        }

        

        if (index == size) {

            insertAtTail(val);

            return true;

        }

        

        DoublyListNode* newNode = new DoublyListNode(val);

        DoublyListNode* current = getNode(index - 1);

        

        newNode->next = current->next;

        newNode->prev = current;

        current->next->prev = newNode;

        current->next = newNode;

        

        size++;

        return true;

    }

    

    // 删除头部节点

    bool deleteAtHead() {

        if (!head) return false;

        

        DoublyListNode* temp = head;

        head = head->next;

        

        if (head) {

            head->prev = nullptr;

        } else {

            tail = nullptr; // 链表为空

        }

        

        delete temp;

        size--;

        return true;

    }

    

    // 删除尾部节点

    bool deleteAtTail() {

        if (!tail) return false;

        

        DoublyListNode* temp = tail;

        tail = tail->prev;

        

        if (tail) {

            tail->next = nullptr;

        } else {

            head = nullptr; // 链表为空

        }

        

        delete temp;

        size--;

        return true;

    }

    

    // 删除指定值节点

    bool deleteNode(int val) {

        DoublyListNode* current = head;

        

        while (current) {

            if (current->val == val) {

                if (current == head) {

                    return deleteAtHead();

                } else if (current == tail) {

                    return deleteAtTail();

                } else {

                    current->prev->next = current->next;

                    current->next->prev = current->prev;

                    delete current;

                    size--;

                    return true;

                }

            }

            current = current->next;

        }

        

        return false;

    }

    

    // 删除指定位置节点

    bool deleteAtIndex(int index) {

        if (index < 0 || index >= size) return false;

        

        if (index == 0) return deleteAtHead();

        if (index == size - 1) return deleteAtTail();

        

        DoublyListNode* current = getNode(index);

        current->prev->next = current->next;

        current->next->prev = current->prev;

        

        delete current;

        size--;

        return true;

    }

    

    // 获取指定位置节点

    DoublyListNode* getNode(int index) {

        if (index < 0 || index >= size) return nullptr;

        

        // 优化：从较近的一端开始遍历

        if (index < size / 2) {

            DoublyListNode* current = head;

            for (int i = 0; i < index; i++) {

                current = current->next;

            }

            return current;

        } else {

            DoublyListNode* current = tail;

            for (int i = size - 1; i > index; i--) {

                current = current->prev;

            }

            return current;

        }

    }

    

    // 查找节点

    DoublyListNode* search(int val) {

        DoublyListNode* current = head;

        while (current) {

            if (current->val == val) return current;

            current = current->next;

        }

        return nullptr;

    }

    

    // 更新节点值

    bool update(int oldVal, int newVal) {

        DoublyListNode* node = search(oldVal);

        if (!node) return false;

        

        node->val = newVal;

        return true;

    }

    

    // 获取链表长度

    int getSize() const {

        return size;

    }

    

    // 清空链表

    void clear() {

        while (head) {

            DoublyListNode* temp = head;

            head = head->next;

            delete temp;

        }

        head = tail = nullptr;

        size = 0;

    }

    

    // 正向打印链表

    void printForward() const {

<"wang.j9k5.org.cn"><"zi.j9k5.org.cn"><"xixi.j9k5.org.cn">

        DoublyListNode* current = head;

        cout << "正向: ";

        while (current) {

            cout << current->val;

            if (current->next) cout << " <-> ";

            current = current->next;

        }

        cout << " -> NULL" << endl;

    }

    

    // 反向打印链表

    void printBackward() const {

        DoublyListNode* current = tail;

        cout << "反向: ";

        while (current) {

            cout << current->val;

            if (current->prev) cout << " <-> ";

            current = current->prev;

        }

        cout << " -> NULL" << endl;

    }

};

```

**双向链表高级操作**

```cpp

class AdvancedDoublyLinkedList {

private:

    DoublyListNode* head;

    DoublyListNode* tail;

    

public:

    // 反转双向链表

    void reverse() {

        if (!head || !head->next) return;

        

        DoublyListNode* current = head;

        DoublyListNode* temp = nullptr;

        

        while (current) {

            // 交换前后指针

            temp = current->prev;

            current->prev = current->next;

            current->next = temp;

            

            // 移动到下一个节点（原来的下一个，现在是前一个）

            current = current->prev;

        }

        

        // 交换头尾指针

        if (temp) {

            tail = head;

            head = temp->prev;

        }

    }

    

    // 旋转链表（向右旋转k个位置）

    void rotateRight(int k) {

        if (!head || k == 0) return;

        

        int length = 0;

        DoublyListNode* current = head;

        

        // 计算链表长度

        while (current) {

            length++;

            current = current->next;

        }

        

        k %= length;

        if (k == 0) return;

        

        // 找到新的尾节点

        DoublyListNode* newTail = head;

        for (int i = 1; i < length - k; i++) {

            newTail = newTail->next;

        }

        

        // 找到新的头节点

        DoublyListNode* newHead = newTail->next;

        

        // 执行旋转

        tail->next = head;

        head->prev = tail;

        

        newHead->prev = nullptr;

        newTail->next = nullptr;

        

        head = newHead;

        tail = newTail;

    }

    

    // 交换相邻节点

    void swapPairs() {

        if (!head || !head->next) return;

        

        DoublyListNode* dummy = new DoublyListNode(0);

        dummy->next = head;

        head->prev = dummy;

        

        DoublyListNode* prev = dummy;

        

        while (prev->next && prev->next->next) {

            DoublyListNode* first = prev->next;

            DoublyListNode* second = first->next;

            

            // 执行交换

            first->next = second->next;

            if (second->next) {

                second->next->prev = first;

            }

            

            second->prev = prev;

            second->next = first;

            first->prev = second;

            prev->next = second;

            

            // 更新prev

            prev = first;

        }

        

        head = dummy->next;

        if (head) head->prev = nullptr;

        

        // 更新尾节点

        DoublyListNode* current = head;

        while (current && current->next) {

            current = current->next;

        }

        tail = current;

        

        delete dummy;

    }

    

    // 扁平化多级双向链表

    class Node {

    public:

        int val;

        Node* prev;

        Node* next;

        Node* child;

        Node(int x) : val(x), prev(nullptr), next(nullptr), child(nullptr) {}

    };

    

    Node* flatten(Node* head) {

        if (!head) return nullptr;

        

        Node* current = head;

        

        while (current) {

            if (current->child) {

                Node* next = current->next;

                Node* childList = flatten(current->child);

                

                current->child = nullptr;

                current->next = childList;

                childList->prev = current;

                

                // 找到子链表的末尾

                Node* childTail = childList;

                while (childTail->next) {

                    childTail = childTail->next;

                }

                

                // 连接原链表的剩余部分

                childTail->next = next;

                if (next) next->prev = childTail;

            }

            current = current->next;

        }

        

        return head;

    }

};

```

**LRU缓存实现**

```cpp

class LRUCache {

private:

    struct CacheNode {

        int key;

        int value;

        CacheNode* prev;

        CacheNode* next;

        CacheNode(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}

    };

    

    unordered_map<int, CacheNode*> cacheMap;

    CacheNode* head;

    CacheNode* tail;

    int capacity;

    int size;

    

    // 将节点移动到头部

    void moveToHead(CacheNode* node) {

        if (node == head) return;

        

        // 从当前位置移除

        if (node->prev) node->prev->next = node->next;

        if (node->next) node->next->prev = node->prev;

        

        if (node == tail) {

            tail = node->prev;

        }

        

        // 添加到头部

        node->next = head;

        node->prev = nullptr;

        

        if (head) {

            head->prev = node;

        }

        head = node;

        

        if (!tail) {

            tail = head;

        }

    }

    

    // 添加新节点到头部

    void addToHead(CacheNode* node) {

        node->next = head;

        node->prev = nullptr;

        

        if (head) {

            head->prev = node;

        }

        head = node;

        

        if (!tail) {

            tail = head;

        }

        

        size++;

    }

    

    // 移除尾部节点

    void removeTail() {

        if (!tail) return;

        

        CacheNode* temp = tail;

        

        if (tail->prev) {

            tail = tail->prev;

            tail->next = nullptr;

        } else {

            head = tail = nullptr;

        }

        

        cacheMap.erase(temp->key);

        delete temp;

        size--;

    }

    

public:

    LRUCache(int capacity) : capacity(capacity), size(0), head(nullptr), tail(nullptr) {}

    

    int get(int key) {

        if (cacheMap.find(key) == cacheMap.end()) {

            return -1;

        }

        

        CacheNode* node = cacheMap[key];

        moveToHead(node);

        return node->value;

    }

    

    void put(int key, int value) {

        if (cacheMap.find(key) != cacheMap.end()) {

            // 更新现有节点

            CacheNode* node = cacheMap[key];

            node->value = value;

            moveToHead(node);

        } else {

            // 创建新节点

            CacheNode* newNode = new CacheNode(key, value);

            

            if (size >= capacity) {

                removeTail();

            }

            

            addToHead(newNode);

            cacheMap[key] = newNode;

        }

    }

    

    // 显示缓存内容

    void display() const {

        CacheNode* current = head;

        cout << "LRU Cache: ";

        while (current) {

            cout << "[" << current->key << ":" << current->value << "]";

            if (current->next) cout << " <-> ";

            current = current->next;

        }

        cout << endl;

    }

    

    ~LRUCache() {

        CacheNode* current = head;

        while (current) {

            CacheNode* temp = current;

            current = current->next;

            delete temp;

        }

    }

};

```

**链表排序算法**

```cpp

class LinkedListSort {

public:

    // 归并排序链表

    static ListNode* sortList(ListNode* head) {

        if (!head || !head->next) return head;

        

        // 找到中点

        ListNode* slow = head;

        ListNode* fast = head->next;

        

        while (fast && fast->next) {

            slow = slow->next;

            fast = fast->next->next;

        }

        

        ListNode* mid = slow->next;

        slow->next = nullptr;

        

        // 递归排序两半

        ListNode* left = sortList(head);

        ListNode* right = sortList(mid);

        

        // 合并有序链表

        return mergeTwoLists(left, right);

    }

    

    // 插入排序链表

    static ListNode* insertionSortList(ListNode* head) {

        if (!head || !head->next) return head;

        

        ListNode* dummy = new ListNode(0);

        ListNode* current = head;

        

        while (current) {

            ListNode* next = current->next;

            ListNode* prev = dummy;

            

            // 在已排序部分找到插入位置

            while (prev->next && prev->next->val < current->val) {

                prev = prev->next;

            }

            

            // 插入节点

            current->next = prev->next;

            prev->next = current;

            

            current = next;

        }

        

        ListNode* result = dummy->next;

        delete dummy;

        return result;

    }

    

    // 重排链表：L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

    static void reorderList(ListNode* head) {

        if (!head || !head->next) return;

        

        // 找到中点

        ListNode* slow = head;

        ListNode* fast = head;

        

        while (fast && fast->next) {

            slow = slow->next;

            fast = fast->next->next;

        }

        

        // 反转后半部分

        ListNode* secondHalf = reverseIterative(slow->next);

        slow->next = nullptr;

        

        // 合并两个链表

        ListNode* firstHalf = head;

        

        while (secondHalf) {

            ListNode* temp1 = firstHalf->next;

            ListNode* temp2 = secondHalf->next;

            

            firstHalf->next = secondHalf;

            secondHalf->next = temp1;

            

            firstHalf = temp1;

            secondHalf = temp2;

        }

    }

};

```

**链表综合应用**

```cpp

class ComplexLinkedListOperations {

public:

    // 复制带随机指针的链表

    class RandomListNode {

    public:

        int val;

        RandomListNode* next;

        RandomListNode* random;

        RandomListNode(int x) : val(x), next(nullptr), random(nullptr) {}

    };

    

    RandomListNode* copyRandomList(RandomListNode* head) {

        if (!head) return nullptr;

        

        // 第一步：在每个节点后插入复制节点

        RandomListNode* current = head;

        while (current) {

            RandomListNode* copy = new RandomListNode(current->val);

            copy->next = current->next;

            current->next = copy;

            current = copy->next;

        }

        

        // 第二步：复制random指针

        current = head;

        while (current) {

            if (current->random) {

                current->next->random = current->random->next;

            }

            current = current->next->next;

        }

        

        // 第三步：分离两个链表

        RandomListNode* dummy = new RandomListNode(0);

        RandomListNode* copyCurrent = dummy;

        current = head;

        

        while (current) {

            copyCurrent->next = current->next;

            copyCurrent = copyCurrent->next;

            

            current->next = current->next->next;

            current = current->next;

        }

        

        RandomListNode* result = dummy->next;

        delete dummy;

        return result;

    }

    

    // 删除链表倒数第N个节点

    ListNode* removeNthFromEnd(ListNode* head, int n) {

        ListNode* dummy = new ListNode(0);

        dummy->next = head;

        

        ListNode* fast = dummy;

        ListNode* slow = dummy;

        

        // 快指针先走n+1步

        for (int i = 0; i <= n; i++) {

            if (!fast) return head; // n超出范围

            fast = fast->next;

        }

        

        // 同时移动快慢指针

        while (fast) {

            slow = slow->next;

            fast = fast->next;

        }

        

        // 删除节点

        ListNode* toDelete = slow->next;

        slow->next = slow->next->next;

        delete toDelete;

        

        ListNode* result = dummy->next;

        delete dummy;

        return result;

    }

};

```

**性能分析与测试**

```cpp

class LinkedListBenchmark {

public:

    static void benchmarkOperations(int operationCount) {

        cout << "链表操作性能测试 (" << operationCount << " 次操作)" << endl;

        cout << "=" << 50 << endl;

        

        // 单向链表测试

        auto start = chrono::high_resolution_clock::now();

        SinglyLinkedList sll;

        

        for (int i = 0; i < operationCount; i++) {

            sll.insertAtTail(i);

        }

        

        for (int i = 0; i < operationCount; i++) {

            sll.deleteNode(i);

        }

        

        auto end = chrono::high_resolution_clock::now();

        auto sllTime = chrono::duration_cast<chrono::milliseconds>(end - start);

        

        // 双向链表测试

        start = chrono::high_resolution_clock::now();

        DoublyLinkedList dll;

        

        for (int i = 0; i < operationCount; i++) {

            dll.insertAtTail(i);

        }

        

        for (int i = 0; i < operationCount; i++) {

            dll.deleteNode(i);

        }

        

        end = chrono::high_resolution_clock::now();

        auto dllTime = chrono::duration_cast<chrono::milliseconds>(end - start);

        <"uou.j9k5.org.cn"><"yty.j9k5.org.cn"><"asa.j9k5.org.cn">

        cout << "单向链表: " << sllTime.count() << "ms" << endl;

        cout << "双向链表: " << dllTime.count() << "ms" << endl;

        

        // 算法性能测试

        cout << "\n算法性能测试" << endl;

        cout << "-" << 30 << endl;

        

        ListNode* head = createList(operationCount);

        

        start = chrono::high_resolution_clock::now();

        LinkedListAlgorithms::reverseIterative(head);

        end = chrono::high_resolution_clock::now();

        auto reverseTime = chrono::duration_cast<chrono::microseconds>(end - start);

        

        cout << "链表反转: " << reverseTime.count() << "μs" << endl;

    }

    

private:

    static ListNode* createList(int n) {

        ListNode* dummy = new ListNode(0);

        ListNode* current = dummy;

        

        for (int i = 1; i <= n; i++) {

            current->next = new ListNode(i);

            current = current->next;

        }

        

        ListNode* result = dummy->next;

        delete dummy;

        return result;

    }

};

```

**总结与最佳实践**

1. **选择原则**：

   - 单向链表适合简单遍历和顺序操作

   - 双向链表适合需要前后遍历的场景

   - 循环链表适合环形数据结构需求

2. **算法复杂度**：

   - 访问：O(n)

   - 插入/删除（已知位置）：O(1)

   - 查找：O(n)

3. **实战建议**：

   - 使用虚拟头节点简化边界处理

   - 注意内存泄漏问题，及时释放节点

   - 考虑使用智能指针自动管理内存

   - 大链表操作时注意递归深度

4. **常见问题解决方案**：

   - 快慢指针解决环检测、中点查找

   - 递归或迭代实现链表反转

   - 归并排序实现链表高效排序

   - 哈希表辅助解决复杂链表问题

链表作为基础数据结构，其算法实现和优化技巧是程序员必备技能。掌握单向链表的各种算法和双向链表的实现细节，能够帮助开发者在面对不同问题时选择最合适的解决方案。