本文首發(fā)于 個(gè)人博客

鏈表只是一種數(shù)據(jù)結(jié)構(gòu)，如果要通過數(shù)據(jù)結(jié)構(gòu)來解決問題那就是算法了，所以這篇文章我們看看如何利用鏈表的數(shù)據(jù)結(jié)構(gòu)去解決一些問題。 以下的代碼均可 前往下載

合并有序鏈表

將2個(gè)遞增的有序鏈表合并為一個(gè)有序鏈表; 要求結(jié)果鏈表仍然使用兩個(gè)鏈表的存儲空間,不另外占用其他的存儲空間. 表中不允許有重復(fù)的數(shù)據(jù)

其實(shí)題目理解起來很簡單 ，如果 La = {1,2,3,,6,9} ,Lb = {2,3,4,5,7,10} 那么合并后應(yīng)該是Lc ={1,2,3,4,6,7,9,10},其規(guī)定不另外占用其他存儲空間，那么我們就只能使用a，b這兩個(gè)存儲空間做手腳。

用 pa 和 pb 分別指向 La 和 Lb ，從首元節(jié)點(diǎn)開始比較，讓Lc指向其中較小的值，并讓較小的值依次后移，直到其中一個(gè)鏈表循環(huán)完畢，那么如果還有多余的數(shù)據(jù)，一定是比較大的，直接接在Lc后面即可：

Status MergeList(LinkList *La,LinkList *Lb,LinkList *Lc) {
    // 找到首元節(jié)點(diǎn)，依次遍歷
    Node *pa = (*La)->next;
    Node *pb = (*Lb)->next;
    // 由于不能開辟新的空間，我們借用La的空間
    Node *pc = *La;
    // pc是一個(gè)局部變量 保存的是Lc的尾節(jié)點(diǎn)，每次都指向兩個(gè)值中的最小值，如果相等則保持其一，刪除釋放另外一個(gè)
    while (pa && pb) {
        if (pa->data < pb->data) {
            pc->next = pa;
            pc = pa;// 這地方相當(dāng)于pc = pc->next 也就是說pc指針也要后移
            pa = pa->next;
        } else if (pa->data > pb->data) {
            pc->next = pb;
            pc = pb;
            pb = pb->next;
        } else {
            Node *temp = pb;
            pc->next = pa;
            pc = pa;
            pa = pa->next;
            pb = pb->next;
            free(temp);
        }
    }

    // 最后多余的數(shù)據(jù)一定是后續(xù)最大的
    pc->next = pa?pa:pb;
    *Lc = *La;
    return SUCCESS;
}

驗(yàn)證：

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    // 算法題1
    LinkList la,lb,lc;
    InitList(&la);
    InitList(&lb);
    InitList(&lc);
    for (int i = 6; i > 0; i --) {
        ListInsert(&la, 1, i);
    }
    printf("打印la ：\n");
    ListTraverse(la);

    for (int i = 10; i > 2; i-=2) {
        ListInsert(&lb, 1, i);
    }
    printf("打印lb ：\n");
    ListTraverse(lb);

    MergeList(&la, &lb, &lc);
    printf("打印lc ：\n");
    ListTraverse(lc);
    return 0;
}
-----------------------------打印結(jié)果
Hello, World!
打印la ：
1  2  3  4  5  6  
打印lb ：
4  6  8  10  
打印lc ：
1  2  3  4  5  6  8  10  
Program ended with exit code: 0

求交集

已知兩個(gè)鏈表A和B分別表示兩個(gè)集合.其元素遞增排列. 設(shè)計(jì)一個(gè)算法,用于求出A與B的交集,并存儲在A鏈表中;

例如: La = {2,4,6,8}; Lb = {4,6,8,10}; => Lc = {4,6,8}

其實(shí)思路跟上面那道題差不多，也是用兩個(gè)指針從前往后依次遍歷，具體看代碼，內(nèi)部有詳細(xì)注釋

Status Intersection(LinkList *La,LinkList *Lb,LinkList *Lc) {
    Node *pa = (*La)->next;
    Node *pb = (*Lb)->next;
    Node *pc = *La;
    Node *temp;
    while (pa && pb) {
        // 每次碰到小的就過濾掉并釋放
        if (pa->data < pb->data) {
            temp = pa;
            pa = pa->next;
            free(temp);
        } else if (pa->data > pb->data) {
            temp = pb;
            pb = pb->next;
            free(temp);
        } else {
            // 碰到相等的保留其中一個(gè)并釋放另外一個(gè)
            pc->next = pa;
            pc = pc->next;
            pa = pa->next;
            temp = pb;
            pb = pb->next;
            free(temp);
        }
    }
    // 要額外判斷多余的情況
    while (pa) {
        temp = pa;
        pa = pa->next;
        free(temp);
    }

    while (pb) {
        temp = pb;
        pb = pb->next;
        free(temp);
    }
    *Lc = *La;
    return SUCCESS;
}

驗(yàn)證：

int main(int argc, const char * argv[]) {
    LinkList la,lb,lc;
    InitList(&la);
    InitList(&lb);
    InitList(&lc);
    for (int i = 6; i > 0; i --) {
        ListInsert(&la, 1, i);
    }
    printf("打印la ：\n");
    ListTraverse(la);

    for (int i = 10; i > 2; i-=2) {
        ListInsert(&lb, 1, i);
    }
    printf("打印lb ：\n");
    ListTraverse(lb);

    Intersection(&la, &lb, &lc);
    printf("打印lc ：\n");
    ListTraverse(lc);
    return 0;
}
--------------------------- 打印結(jié)果
打印la ：
1  2  3  4  5  6  
打印lb ：
4  6  8  10  
打印 lc ：
4  6  

鏈表倒序

設(shè)計(jì)一個(gè)算法,將鏈表中所有節(jié)點(diǎn)的鏈接方向"原地旋轉(zhuǎn)",即要求僅僅利用原表的存儲空間. 換句話說,要求算法空間復(fù)雜度為O(1);

這里的空間復(fù)雜度 O(1) 其實(shí)也是一樣，不允許新的輔助空間，所以我們還是要在原有的鏈表基礎(chǔ)上做手腳。

之前的文章中我們講過鏈表的初始化有兩種方式：頭插法 和 尾插法 ，最后我們發(fā)現(xiàn)尾插法跟我們?nèi)粘＿壿嫴畈欢啵? 而頭插法卻是倒序的：因?yàn)橄炔迦氲慕Y(jié)點(diǎn)為表尾,后插入的結(jié)點(diǎn)為表頭,即可實(shí)現(xiàn)鏈表的逆轉(zhuǎn);：

void Inverse(LinkList *L) {
    //  頭插法每次要插入的節(jié)點(diǎn)，初始是首元節(jié)點(diǎn)
    Node *target = (*L)->next;
    Node *tNext;
    // 為了讓鏈表的尾結(jié)點(diǎn)指向NULL
    (*L)->next = NULL;
    while (target) {
        // 每次讓tNext保存target之后的數(shù)據(jù)
        tNext = target->next;
        target->next = (*L)->next;
        (*L)->next = target;
        target = tNext;
    }
}

驗(yàn)證

int main(int argc, const char * argv[]) {
    LinkList la,lb,lc;
    InitList(&la);
    InitList(&lb);
    InitList(&lc);
    for (int i = 6; i > 0; i --) {
        ListInsert(&la, 1, i);
    }
    printf("打印la ：\n");
    ListTraverse(la);

    Inverse(&la);
    printf("打印la ：\n");
    ListTraverse(la);
    return 0;
}
------------------------------------打印結(jié)果
打印la ：
1  2  3  4  5  6  
打印la ：
6  5  4  3  2  1  
Program ended with exit code: 0

刪除指定范圍的節(jié)點(diǎn)

設(shè)計(jì)一個(gè)算法,刪除遞增有序鏈表中值大于等于mink且小于等于maxk(mink,maxk是給定的兩個(gè)參數(shù),其值可以和表中的元素相同,也可以不同)的所有元素

其實(shí)思路很簡單，找到左邊最后一個(gè)小于mink的節(jié)點(diǎn)，以及找到右邊第一個(gè)大于maxk的節(jié)點(diǎn)。

void DeleteDataRange(LinkList *L, int min,int max) {
    Node *p = (*L)->next;
    Node *left = *L,*right=NULL;
    // 找到左邊節(jié)點(diǎn)
    while (p && p->data < min) {
        left = p;
        p = p->next;
    }

    // 找到右邊節(jié)點(diǎn)
    while (p && p->data <= max) {
        right = p;
        p = p->next;
    }
    right = right->next;

    // 左邊節(jié)點(diǎn)指向右邊節(jié)點(diǎn)
    left->next = right;

    // 臨時(shí)保存要?jiǎng)h除的節(jié)點(diǎn)進(jìn)行釋放
    Node *temp = left->next;
    while (temp && temp != right) {
        Node *del = temp;
        temp = temp->next;
        free(del);
    }
}

驗(yàn)證

int main(int argc, const char * argv[]) {
    LinkList la,lb,lc;
    InitList(&la);
    InitList(&lb);
    InitList(&lc);
    for (int i = 6; i > 0; i --) {
        ListInsert(&la, 1, i);
    }
    printf("打印la ：\n");
    ListTraverse(la);

    DeleteDataRange(&la, 2, 3);
    printf("打印la ：\n");
    ListTraverse(la);
    return 0;
}
---------------------打印結(jié)果
打印la ：
1  2  3  4  5  6  
打印la ：
1  4  5  6  

調(diào)整次序

設(shè)將n(n>1)個(gè)整數(shù)存放到一維數(shù)組R中, 試設(shè)計(jì)一個(gè)在時(shí)間和空間兩方面都盡可能高效的算法;將R中保存的序列循環(huán)左移p個(gè)位置(0<p<n)個(gè)位置, 即將R中的數(shù)據(jù)由(x0,x1,......,xn-1)變換為(xp,xp+1,...,xn-1,x0,x1,...,xp-1)

阿西吧！，這段描述完全看不懂有沒有，其實(shí)簡化一下是這樣：

例如:
 pre[10] = {0,1,2,3,4,5,6,7,8,9},
 n = 10,p = 3;
 pre[10] = {3,4,5,6,7,8,9,0,1,2}

數(shù)組循環(huán)往左移動多少位，左邊位置固定，超出的移到數(shù)組后面。注意：有的同學(xué)可能會想我用兩個(gè)指針指向鏈表的兩個(gè)位置進(jìn)行重新排列就好了啊，這里題目中要求是數(shù)組而不是鏈表，所以不能用鏈表的方法去解決問題。

// 將數(shù)組指定范圍的數(shù)據(jù)進(jìn)行倒序
void Reverse (int *array,int left,int right ) {
    int i = left,j = right ;
    // 首位對調(diào)
    int temp;
    while (i < j) {
        temp = array[i];
        array[i] = array[j];
        array[j] = temp;
        // i右移  j左移
        i++;
        j--;
    }
}
//將長度為n的數(shù)組pre 中的數(shù)據(jù)循環(huán)左移p個(gè)位置
void LeftShift(int *pre,int n,int p){
    // 比如 {1,2,3,4,5} 向左移2位
    if (p > 0 && p < n) {
        // 整個(gè)數(shù)組數(shù)據(jù)全部倒序 {5,4,3,2,1}
        Reverse(pre, 0, n-1);
        // 前部分倒序 {3,4,5,2,1}
        Reverse(pre, 0, n-p-1);
        // 后部分倒序 {3,4,5,1,2}
        Reverse(pre, n-p, n-1);
    }
}

其實(shí)就是反復(fù)利用倒序的函數(shù)對數(shù)組進(jìn)行調(diào)整,這里就不做驗(yàn)證了，請自行去驗(yàn)證一下即可。

找元素

已知一個(gè)整數(shù)序列A = (a0,a1,a2,...an-1),其中(0<= ai <=n),(0<= i<=n). 若存在ap1= ap2 = ...= apm = x,且m>n/2(0<=pk<n,1<=k<=m),則稱x 為 A的主元素. 例如,A = (0,5,5,3,5,7,5,5),則5是主元素; 若B = (0,5,5,3,5,1,5,7),則A 中沒有主元素,假設(shè)A中的n個(gè)元素保存在一個(gè)一維數(shù)組中,請?jiān)O(shè)計(jì)一個(gè)盡可能高效的算法,找出數(shù)組元素中的主元素,若存在主元素則輸出該元素,否則輸出-1.

其實(shí)有點(diǎn)像消消樂的算法，找到當(dāng)前符合規(guī)定的元素，如果存在輸出（消消樂消除），不存在返回-1。題目中提示盡可能高效，意思就是優(yōu)先滿足時(shí)間復(fù)雜度，所以我們可以考慮用空間換時(shí)間。

題目分析: 主元素,是數(shù)組中的出現(xiàn)次數(shù)超過一半的元素; 當(dāng)數(shù)組中存在主元素時(shí),所有非主元素的個(gè)數(shù)和必少于一半. 如果讓主元素和一個(gè)非主元素配對, 則最后多出來的元素(沒有元素與之匹配就是主元素.

int MainElement(int *A, int n){

    //目標(biāo): 求整數(shù)序列A中的主元素;
    //count 用來計(jì)數(shù)
    int count = 1;
    //key 用來保存候選主元素, 初始A[0]
    int key = A[0];

    //(1) 掃描數(shù)組,選取候選主元素
    for (int i = 1; i < n; i++) {
        //(2) 如果A[i]元素值 == key ,則候選主元素計(jì)數(shù)加1;
        if (A[i] == key) {
            count++;
        }else{
            //(3) 當(dāng)前元素A[i] 非候選主元素,計(jì)數(shù)減1;
            if(count >0){
                count--;

            }else{
               //(4) 如果count 等于0,則更換候選主元素,重新計(jì)數(shù)
                key = A[i];
                count = 1;
            }

        }
    }

    //如果count >0
    if (count >0){
        //(5)統(tǒng)計(jì)候選主元素的實(shí)際出現(xiàn)次數(shù)
        for (int i = count = 0; i < n; i++)
            if (A[i] == key) count++;
    }

    //(6)判斷count>n/2, 確認(rèn)key是不是主元素
    if (count > n/2) return key;
    else return -1; //不存在主元素

}

鏈表去重

用單鏈表保存m個(gè)整數(shù), 結(jié)點(diǎn)的結(jié)構(gòu)為(data,link),且|data|<=n(n為正整數(shù)). 現(xiàn)在要去設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度盡可能高效的算法. 對于鏈表中的data 絕對值相等的結(jié)點(diǎn), 僅保留第一次出現(xiàn)的結(jié)點(diǎn),而刪除其余絕對值相等的結(jié)點(diǎn).例如,鏈表A = {21,-15,15,-7,15}, 刪除后的鏈表A={21,-15,-7}

題目分析:

要求設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度盡量高效的算法,而已知|data|<=n, 所以可以考慮用空間換時(shí)間的方法. 申請一個(gè)空間大小為n+1(0號單元不使用)的輔助數(shù)組. 保存鏈表中已出現(xiàn)的數(shù)值,通過對鏈表進(jìn)行一趟掃描來完成刪除.

void DeleteEqualNode(LinkList *L,int n) {
    int *p = malloc(sizeof(int)*n);
    for (int i = 0; i < n; i ++) {
        *(p+i) = 0;
    }
    // r 指向頭節(jié)點(diǎn)
    Node *r = *L;
    // 首元節(jié)點(diǎn)
    Node *temp = (*L)->next;
    while (temp) {
        ListData absData = abs(temp->data);
        if (p[absData] == 1) {// 說明已經(jīng)有值了
            r->next = temp->next;
            free(temp);
        } else {
            p[absData] = 1;
            r = temp;
        }
        temp = temp->next;
    }
}

其實(shí)相當(dāng)于把數(shù)字的絕對值作為數(shù)組下標(biāo)保存起來，內(nèi)部的值只有0和1，這樣就可以遍歷的過程中直接取值進(jìn)行比較，速度會非?？欤瑹o非就是初始化的時(shí)候需要一個(gè)大小為n的數(shù)組空間

總結(jié)

以上就是最近學(xué)習(xí)的鏈表相關(guān)的知識運(yùn)用以及相關(guān)的問題解答，后續(xù)有相關(guān)的題目還會陸續(xù)更新。