链表进阶：双向链表、循环链表、链表的反转操作

说实话，单链表虽然好用，但真到了实战项目里，你很快就会发现它有点「不够用」。我记得刚入行那会儿，用单链表做任务队列，每次要删除某个节点都得从头遍历找前驱节点，那个效率低得让人抓狂。后来老工程师甩给我一句话：「小子，试试双向链表。」

嗯，这一章我们就来聊聊链表的进阶玩法。双向链表、循环链表，还有那个面试最爱考的链表反转。我会把我在项目中踩过的坑、总结的技巧都抖出来。

一、双向链表：给节点装上「前后眼」

双向链表，说白了就是在每个节点里多存一个指针——指向前一个节点。你想想看，单链表只能往后走，双向链表可以往前走，这就灵活多了。

// 双向链表节点
typedef struct DNode {
    int data;
    struct DNode *prev;  // 前驱指针
    struct DNode *next;  // 后继指针
} DNode;

我在做嵌入式设备的数据缓存时，就吃过单链表的亏。当时需要频繁删除尾部节点，单链表得遍历到倒数第二个节点才能删，O(n)的时间复杂度在实时系统里根本扛不住。换成双向链表后，直接通过尾指针就能O(1)删除，爽多了。

双向链表的插入操作

插入操作比单链表多一步——要同时更新新节点的prev和next，还要调整前后节点的指针。我建议你画个图再写代码，不然很容易搞乱指针指向。

// 在节点 p 后面插入新节点 newNode
void insertAfter(DNode *p, DNode *newNode) {
    if (p == NULL || newNode == NULL) return;
    
    newNode->next = p->next;
    newNode->prev = p;
    
    if (p->next != NULL) {
        p->next->prev = newNode;  // 这步容易忘！
    }
    p->next = newNode;
}

双向链表的删除操作

删除操作就优雅多了。因为有了prev指针，你不需要像单链表那样找前驱节点。直接拿着目标节点就能删。

// 删除节点 del
void deleteNode(DNode *del) {
    if (del == NULL) return;
    
    if (del->prev != NULL) {
        del->prev->next = del->next;
    }
    if (del->next != NULL) {
        del->next->prev = del->prev;
    }
    free(del);
}

你看，代码比单链表简洁不少吧？但要注意，如果删除的是头节点，你得额外更新头指针。

二、循环链表：让链表「首尾相连」

循环链表，就是把尾节点的next指向头节点。如果是双向循环链表，头节点的prev还要指向尾节点。说白了，就是让链表变成一个环。

我为什么喜欢循环链表？因为它在需要「轮询」的场景下特别好用。比如操作系统的任务调度，每个任务轮流执行，用循环链表天然就支持这种逻辑。

// 遍历循环链表
void traverseCircular(DNode *head) {
    if (head == NULL) return;
    
    DNode *p = head;
    do {
        printf("%d ", p->data);
        p = p->next;
    } while (p != head);  // 注意：用 do-while 保证至少执行一次
}

嗯，这里要注意。用while循环的话，你得先处理头节点再进入循环，不然第一次判断就退出了。我个人习惯用do-while，代码更干净。

三、链表的反转操作

链表反转，面试题里的常客。我当年面试时就被问过，当时手写代码还出了bug，尴尬得很。后来我总结了一套「三指针法」，再也没写错过。

单链表的反转

核心思路：用三个指针——prev、curr、next——依次把每个节点的next指向前一个节点。

// 反转单链表
Node* reverseList(Node *head) {
    Node *prev = NULL;
    Node *curr = head;
    Node *next = NULL;
    
    while (curr != NULL) {
        next = curr->next;   // 先保存下一个节点
        curr->next = prev;   // 反转指针
        prev = curr;         // 前移
        curr = next;         // 前移
    }
    return prev;  // 新的头节点
}

你想想看，这个过程中最关键的一步是什么？是 next = curr->next。如果不先保存next，等你把curr->next指向prev后，后面的节点就找不到了。我曾经在项目里写过一个类似的逻辑，忘了保存next，结果链表后半截全丢了，调试了一下午才找到原因。

双向链表的反转

双向链表反转其实更简单——把每个节点的prev和next互换就行了。

// 反转双向链表
DNode* reverseDList(DNode *head) {
    DNode *curr = head;
    DNode *temp = NULL;
    
    while (curr != NULL) {
        // 交换 prev 和 next
        temp = curr->prev;
        curr->prev = curr->next;
        curr->next = temp;
        
        // 移动到下一个节点（注意：此时下一个节点是 prev）
        curr = curr->prev;
    }
    
    // 返回新的头节点
    if (temp != NULL) {
        head = temp->prev;
    }
    return head;
}

四、知识体系总览

下面这张图是我画的本章知识结构，你可以对照着梳理一下思路。

五、实战中的选择建议

说了这么多，到底什么时候用哪种链表？我根据项目经验给你列个表：

场景	推荐类型	原因
频繁删除尾部节点	双向链表	O(1)删除，无需遍历
任务轮询调度	循环链表	天然支持循环遍历
内存极度受限	单链表	少一个指针，省空间
需要双向遍历	双向链表	前后都能走
面试手写代码	单链表反转	考基本功，三指针法必会

好了，这一章的内容就到这儿。双向链表、循环链表、反转操作，这三个知识点你掌握了吗？代码多写几遍，尤其是反转操作，画图+手写代码，比光看强十倍。

---