復(fù)雜鏈表的復(fù)制問(wèn)題

• 引言
• 問(wèn)題描述
• 思路分析
• • 思路一：
  • 思路二：
  • • 圖解：
• 代碼實(shí)現(xiàn)
• 總結(jié)

創(chuàng)新互聯(lián)專注于企業(yè)成都全網(wǎng)營(yíng)銷、網(wǎng)站重做改版、建陽(yáng)網(wǎng)站定制設(shè)計(jì)、自適應(yīng)品牌網(wǎng)站建設(shè)、H5響應(yīng)式網(wǎng)站、購(gòu)物商城網(wǎng)站建設(shè)、集團(tuán)公司官網(wǎng)建設(shè)、外貿(mào)營(yíng)銷網(wǎng)站建設(shè)、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁(yè)設(shè)計(jì)等建站業(yè)務(wù)，價(jià)格優(yōu)惠性價(jià)比高，為建陽(yáng)等各大城市提供網(wǎng)站開(kāi)發(fā)制作服務(wù)。引言

小編學(xué)習(xí)了這么久單鏈表感覺(jué)自我良好，想著刷道題測(cè)試一下，看到了一個(gè)中等難度的題目，小編想著嘗試一下，結(jié)果被瞬間打臉！讀懂題目都花了好長(zhǎng)時(shí)間，思路更是斷斷續(xù)續(xù)的，結(jié)合題解并研究了一段時(shí)間后，把這道題目的解析分享給大家。

問(wèn)題描述

給你一個(gè)長(zhǎng)度為 n 的鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針 random ，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值，以及兩個(gè)指針，一個(gè)指向下一個(gè)節(jié)點(diǎn)，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)），返回結(jié)果為復(fù)制后復(fù)雜鏈表的head。

總的來(lái)說(shuō)就是讓你把鏈表拷貝一份，與以往不同的是，多了一個(gè)隨機(jī)指針random,需要判斷random的指向。

思路分析 思路一：

先把原鏈表每個(gè)結(jié)點(diǎn)拷貝下來(lái)，再去判斷random的指向，這個(gè)時(shí)候的時(shí)間復(fù)雜度就比較高了，拷貝原鏈表是O(n),判斷random指向的時(shí)候，最壞的情況每個(gè)random都指向最后一個(gè)，經(jīng)典的O(n^2)。

思路二：

分步走：
①在原鏈表的基礎(chǔ)上，在每個(gè)節(jié)點(diǎn)的后面，復(fù)制前面的結(jié)點(diǎn)，并將其與原鏈表鏈接。
②判斷隨機(jī)指針random的指向。
③將拷貝的結(jié)點(diǎn)從原鏈表中分離出來(lái)，返回新鏈表的指針。
該思路時(shí)間復(fù)雜度為O(n).

圖解：

第一步：在原鏈表上復(fù)制鏈表

第二步：判斷random指向（問(wèn)題的關(guān)鍵）
紅色線代表random指向

第三步：分離鏈表（利用哨兵位尾插）

下面結(jié)合代碼深入理解一下

代碼實(shí)現(xiàn)

//在每個(gè)源節(jié)點(diǎn)的后面創(chuàng)建一個(gè)拷貝結(jié)點(diǎn)
    struct Node* cur=head;
    
    while(cur){struct Node* newnode=(struct Node*)malloc(sizeof(struct Node));
        struct Node* next=cur->next;
        newnode->val=cur->val;
        //鏈接拷貝的結(jié)點(diǎn)
        cur->next=newnode;
        newnode->next=next;

        cur=next;
    }

//處理拷貝結(jié)點(diǎn)random
    cur=head;
    while(cur){struct Node* copy=cur->next;
        if(cur->random==NULL){copy->random=NULL;
        }
        else{copy->random=cur->random->next;
        }
        cur=cur->next->next;
    }

//將拷貝的鏈表分離出來(lái)
    cur=head;
    struct Node* rhead,*tail;
    rhead=tail=(struct Node*)malloc(sizeof(struct Node));
    rhead->next=NULL;
    while(cur){struct Node* copy=cur->next;
        struct Node* next=copy->next;
        //保護(hù)原鏈表結(jié)構(gòu)
        cur->next=next;
        //分離出新鏈表
        tail->next=copy;
        tail=tail->next;
        cur=next;
    }
    tail->next=NULL;
    struct Node* new=rhead->next;
    free(rhead);
    return new;

總結(jié)

本題的難度一是思路難，二是代碼編寫困難，需要根據(jù)圖分析相對(duì)聯(lián)系，比如：分析random指向的時(shí)候，需要（copy->random=cur->random->next;），拷貝結(jié)點(diǎn)的random要指向原節(jié)點(diǎn)random指向節(jié)點(diǎn)的下一個(gè)哦。理清思路，反復(fù)思考是解題的關(guān)鍵。

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站欄目：?jiǎn)捂湵碇畯?fù)雜鏈表的復(fù)制（C語(yǔ)言版）-創(chuàng)新互聯(lián)
分享URL：http://weahome.cn/article/docidd.html