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

一、双向链表核心概念单向链表只能从头往后走不能回头。双向链表每个节点有前驱指针 后继指针可以从头往后、从尾往前双向遍历任意节点删除、查找更方便结构稍微复杂一点但实用性更强节点结构数据域 前驱 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; }六、今日笔试面试考点双向链表可双向遍历删除节点效率比单链表高双向链表操作务必维护prev 和 next两个指针防止断链链表反转迭代版优先背诵工作刷题都用它递归反转理解思路即可大数据量容易栈溢出链表反转是笔试原题高频考点必须默写熟练七、今日总结双向链表多一个前驱指针支持双向遍历优势删除、反向遍历更方便链表反转掌握迭代万能模板直接套所有题链表反转是后续回文链表、k 个一组反转的基础