第C語言算法學(xué)習(xí)之雙向鏈表詳解目錄一、練習(xí)題目二、算法思路1、設(shè)計瀏覽器歷史記錄2、扁平化多級雙向鏈表3、展平多級雙向鏈表4、二叉搜索樹與雙向鏈表

一、練習(xí)題目

題目鏈接難度1472.設(shè)計瀏覽器歷史記錄★★★☆☆430.扁平化多級雙向鏈表★★★☆☆劍指OfferII028.展平多級雙向鏈表★★★☆☆劍指Offer36.二叉搜索樹與雙向鏈表★★★★☆

二、算法思路

1、設(shè)計瀏覽器歷史記錄

1.這是一個模擬題；

2.初始化生成一個頭結(jié)點，記錄一個當(dāng)前結(jié)點；

3.向前和向后是兩個類似的過程，可以統(tǒng)一實現(xiàn)，注意一些邊界條件。

structNode{

stringval;

Node*prev;

Node*next;

classBrowserHistory{

Node*List,*Current;

public:

BrowserHistory(stringhomepage){

List=newNode();

List-prev=List-next=nullptr;

List-val=homepage;

Current=List;

voidvisit(stringurl){

Node*Next=Current-next;

if(Next==nullptr){

Current-next=newNode();

Current-next-next=nullptr;

Current-next-prev=Current;

}else{

Node*tmp=Next-next;

Next-next=nullptr;

//free

while(tmp){

Node*node=tmp-next;

deletetmp;

tmp=node;

Current-next-val=url;

Current=Current-next;

stringback(intsteps){

stringstr=Current-

Node*pre;

while(steps--Current){

pre=Current;

Current=Current-prev;

if(Current)str=Current-

if(nullptr==Current)Current=pre;

returnstr;

stringforward(intsteps){

stringstr=Current-

Node*pre;

while(steps--Current){

pre=Current;

Current=Current-next;

if(Current)str=Current-

if(nullptr==Current)Current=pre;

returnstr;

};

2、扁平化多級雙向鏈表

1.利用一個遞歸函數(shù)last=dfs(now)，一旦遇到child域非空的結(jié)點，則遞歸計算clast=dfs(now-child)，返回值是遞歸展平后的最后一個結(jié)點，然后進(jìn)行雙向鏈表的鏈接操作。

2.例如，當(dāng)前有child域的結(jié)點為now，它的下一個結(jié)點是next，遞歸計算以后得到展平的鏈表的最后一個結(jié)點為clast，則有如下關(guān)系：

nownow-child...clastnext

3.根據(jù)以上關(guān)系調(diào)整雙向鏈表，注意不要忘記將child域置空。

4.當(dāng)遍歷到這個雙向鏈表的最后一個結(jié)點的時候，如果它有child域，則當(dāng)前鏈表的最后一個結(jié)點就是clast，否則就是它自己now；

classSolution{

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...cLastnext;

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;

returnlast;

public:

Node*flatten(Node*head){

if(head==nullptr){

returnnullptr;

Node*last=dfs(head);

last-next=nullptr;

returnhead;

};

3、展平多級雙向鏈表

（1）同上一題。

4、二叉搜索樹與雙向鏈表

（1）遇到這樣的題，首先需要設(shè)計好遞歸函數(shù)；

（2）像這個問題，對于左子樹和右子樹，需要知道雙向鏈表的頭結(jié)點和尾結(jié)點，所以遞歸的時候需要返回兩個值，于是可以直接采用函數(shù)傳指針進(jìn)行返回，由于二叉樹的結(jié)點本身就是指針，所以需要傳二級指針；

（3）遞歸計算左子樹變成雙向鏈表的情況；

（4）遞歸計算右子樹變成雙向鏈表的情況；

（5）將左子樹的雙向鏈表鏈接到root左邊，將右子樹的雙向鏈表鏈接到root右邊，然后根據(jù)遞歸函數(shù)的實際作用，返回頭結(jié)點和尾結(jié)點。

classSolution{

voiddfs(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