当前位置：首页 > news >正文

深入解析双向链表与反转算法

news 2026/5/7 16:26:06

一、双向链表核心概念

单向链表：只能从头往后走，不能回头。双向链表：每个节点有前驱指针 + 后继指针

可以从头往后、从尾往前双向遍历
任意节点删除、查找更方便
结构稍微复杂一点，但实用性更强

节点结构：数据域 + 前驱 prev 指针 + 后继 next 指针

二、双向链表节点定义

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

三、双向链表基础操作实现

1. 尾插法创建双向链表

DListNode* createDList() { DListNode* dummy = new DListNode(0); DListNode* cur = dummy; cur->next = new DListNode(10); cur->next->prev = cur; cur = cur->next; cur->next = new DListNode(20); cur->next->prev = cur; cur = cur->next; cur->next = new DListNode(30); cur->next->prev = cur; return dummy->next; }

2. 正向、反向遍历

// 正向遍历 void printForward(DListNode* head) { DListNode* cur = head; while(cur) { cout << cur->val << " "; cur = cur->next; } cout << endl; } // 反向遍历 void printBackward(DListNode* tail) { DListNode* cur = tail; while(cur) { cout << cur->val << " "; cur = cur->prev; } cout << endl; }

3. 头部插入节点

DListNode* addHead(DListNode* head, int val) { DListNode* newNode = new DListNode(val); newNode->next = head; if(head) head->prev = newNode; return newNode; }

4. 删除指定节点

双向链表删除不用从头遍历定位前一个节点，直接自删：

void delNode(DListNode* node) { DListNode* p = node->prev; DListNode* n = node->next; p->next = n; if(n) n->prev = p; delete node; }

四、算法重点：单链表反转（必考万能模板）

迭代版（笔试首选、无递归栈溢出风险）

ListNode* reverseList(ListNode* head) { ListNode* pre = nullptr; ListNode* cur = head; ListNode* next = nullptr; while(cur != nullptr) { // 保存下一个 next = cur->next; // 反转指向 cur->next = pre; // 双指针后移 pre = cur; cur = next; } return pre; }

必背口诀：存下一个 → 改指向 → 双指针同步后移

递归版（面试常问思路）

ListNode* reverseListRecur(ListNode* head) { if(head == nullptr || head->next == nullptr) return head; ListNode* newHead = reverseListRecur(head->next); head->next->next = head; head->next = nullptr; return newHead; }

五、完整可运行测试代码

#include <iostream> using namespace std; // 双向链表节点 struct DListNode { int val; DListNode* prev; DListNode* next; DListNode(int x) : val(x), prev(nullptr), next(nullptr) {} }; // 单向链表节点（用于反转） struct ListNode { int val; ListNode* next; ListNode(int x) : val(x), next(nullptr) {} }; // 省略上面写的所有函数，直接main测试 int main() { // 双向链表测试 DListNode* dHead = createDList(); cout << "双向链表正向："; printForward(dHead); // 单链表反转测试 ListNode* n1 = new ListNode(1); ListNode* n2 = new ListNode(2); ListNode* n3 = new ListNode(3); n1->next = n2; n2->next = n3; ListNode* res = reverseList(n1); cout << "链表反转后："; while(res) { cout << res->val << " "; res = res->next; } return 0; }