C++ 数据结构与算法：线性表之链表

本文介绍 C++ 链表的数据结构与实现，包括头插尾插、查找删除等操作。分析了链表内存占用与访问效率的优缺点。结合 LeetCode 经典题目，演示了反转链表、删除倒数第 N 个节点、合并有序链表、检测环、求交点及节点交换等算法，重点讲解双指针与快慢指针的应用场景及时间复杂度。

云间漫步发布于 2026/3/28更新于 2026/4/141 浏览

第二章线性表

2.2 链表

链表解决了数组在内存中不能连续存放的问题。链表的时间复杂度：查找 O(n); 删除，插入（头插或尾插）是 O(1)；

2.2.1 实现一个链表

实现一个链表，支持头插入，尾查，查找元素，删除元素，删除所有 value 的元素，打印链表。

// 支持头插入，尾查，查找元素，删除元素，删除所有 value 的元素，反转链表，打印链表
class LinkList {
public:
    LinkList() : m_pHead(new Node(-1)), m_pTailNode(m_pHead) {}
    ~LinkList() {
        // 释放所有链表
        Node* p = m_pHead->next;
        while (p != nullptr) {
            Node* tmp = p;
            p = p->next;
            delete tmp;
        }
        delete m_pHead;
        m_pHead = nullptr;
    }
    // 头插入
    void insertHead(int data) {
        Node* tmp = new Node(data);
        tmp->next = m_pHead->next;
        m_pHead->next = tmp;
        // 更新尾部节点
        if (m_pHead == m_pTailNode) {
            m_pTailNode = tmp;
        }
    }
    // 尾部插入
    void insertTail(int data) {
        Node* tmp = new Node(data);
        m_pTailNode->next = tmp;
        m_pTailNode = tmp;
    }
    // 查找
    bool find(int data) {
        
        Node* firstdata = m_pHead->next;
         (firstdata != ) {
             (firstdata->data == data) {
                 ;
            }
            firstdata = firstdata->next;
        }
         ;
    }
    
    {
        Node* firstdata = m_pHead->next;
        Node* tmp = m_pHead;
         (firstdata != ) {
             (firstdata->data == data) {
                tmp->next = firstdata->next;
                ;
            }
            tmp = firstdata; 
            firstdata = firstdata->next;
        }
    }
    
    {
        Node* firstdata = m_pHead->next;
        Node* tmp = m_pHead;
         (firstdata != ) {
             (firstdata->data == data) {
                tmp->next = firstdata->next;
            }  {
                tmp = firstdata; 
            }
            firstdata = firstdata->next;
        }
    }
    
    {
        Node* p = m_pHead->next;
         (p) { 
            cout << p->data << ;
            p = p->next;
        }
        cout << endl;
    }
:
    
      {
        ( da = ) : (da), () {}
         data;
        Node* next;
    };
    Node* m_pHead;
    Node* m_pTailNode;
    
};
{
    LinkList list;
    list.();
    list.();
    list.();
    list.();
    std::cout << list.() << std::endl;
    std::cout << list.() << std::endl;
    list.();
    list.();
    list.();
    
    list.();
    list.();
}