C语言双向链表
英雄哪里出来 人气:0一、练习题目
题目链接 | 难度 |
---|---|
1472. 设计浏览器历史记录 | ★★★☆☆ |
430. 扁平化多级双向链表 | ★★★☆☆ |
剑指 Offer II 028. 展平多级双向链表 | ★★★☆☆ |
剑指 Offer 36. 二叉搜索树与双向链表 | ★★★★☆ |
二、算法思路
1、设计浏览器历史记录
1.这是一个模拟题;
2.初始化生成一个头结点,记录一个当前结点;
3.向前 和 向后 是两个类似的过程,可以统一实现,注意一些边界条件。
struct Node { string val; Node* prev; Node* next; }; class BrowserHistory { Node * List, *Current; public: BrowserHistory(string homepage) { List = new Node(); List->prev = List->next = nullptr; List->val = homepage; Current = List; } void visit(string url) { Node *Next = Current->next; if(Next == nullptr) { Current->next = new Node(); Current->next->next = nullptr; Current->next->prev = Current; }else { Node *tmp = Next->next; Next->next = nullptr; // free while(tmp) { Node *node = tmp->next; delete tmp; tmp = node; } } Current->next->val = url; Current = Current->next; } string back(int steps) { string str = Current->val; Node *pre; while(steps-- && Current) { pre = Current; Current = Current->prev; if(Current) str = Current->val; } if(nullptr == Current) Current = pre; return str; } string forward(int steps) { string str = Current->val; Node *pre; while(steps-- && Current) { pre = Current; Current = Current->next; if(Current) str = Current->val; } if(nullptr == Current) Current = pre; return str; } };
2、扁平化多级双向链表
1.利用一个递归函数last = dfs(now),一旦遇到child域非空的结点,则递归计算clast = dfs(now->child),返回值是递归展平后的最后一个结点,然后进行双向链表的链接操作。
2.例如,当前有 child域的结点为now,它的下一个结点是next,递归计算以后得到展平的链表的最后一个结点为 clast,则有如下关系:
now <---> now->child ... clast <---> next
3.根据以上关系调整双向链表,注意不要忘记将child域置空。
4.当遍历到这个双向链表的最后一个结点的时候,如果它有child域,则当前链表的最后一个结点就是clast,否则就是它自己now;
class Solution { Node* dfs(Node* head) { Node *now = head; Node *last = nullptr; while(now) { Node *cLast; if(now->child) { cLast = dfs(now->child); Node *next = now->next; // now <--> cFirst ... cLast <---> next; now->next = now->child; now->child = nullptr; now->next->prev = now; if(next) { next->prev = cLast; } cLast->next = next; } if(now->next == nullptr) { if(now->child) { last = cLast; }else { last = now; } } now = now->next; } return last; } public: Node* flatten(Node* head) { if(head == nullptr) { return nullptr; } Node *last = dfs(head); last->next = nullptr; return head; } };
3、展平多级双向链表
(1)同上一题。
4、二叉搜索树与双向链表
(1)遇到这样的题,首先需要设计好递归函数;
(2)像这个问题,对于 左子树 和 右子树,需要知道双向链表的 头结点 和 尾结点,所以递归的时候需要返回 两个值,于是可以直接采用函数传指针进行返回,由于二叉树的结点本身就是指针,所以需要传 二级指针;
(3)递归计算左子树变成双向链表的情况;
(4)递归计算右子树变成双向链表的情况;
(5)将左子树的双向链表链接到root左边,将右子树的双向链表链接到root右边,然后根据递归函数的实际作用,返回 头结点 和 尾结点。
class Solution { void dfs(Node *root, Node **minNode, Node **maxNode) { if(root == nullptr) { *minNode = nullptr; *maxNode = nullptr; return ; } Node *lminNode, *lmaxNode, *rminNode, *rmaxNode; if(root->left) { dfs(root->left, &lminNode, &lmaxNode); lmaxNode->right = root; root->left = lmaxNode; *minNode = lminNode; }else { *minNode = root; } if(root->right) { dfs(root->right, &rminNode, &rmaxNode); rminNode->left = root; root->right = rminNode; *maxNode = rmaxNode; }else { *maxNode = root; } } public: Node* treeToDoublyList(Node* root) { if(root == nullptr) { return nullptr; } Node *minNode, *maxNode; dfs(root, &minNode, &maxNode); maxNode->right = minNode; minNode->left = maxNode; return minNode; } };
加载全部内容