數(shù)據(jù)結(jié)構(gòu):鏈表基礎(chǔ)OJ練習(xí)+帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)

這篇具有很好參考價(jià)值的文章主要介紹了數(shù)據(jù)結(jié)構(gòu):鏈表基礎(chǔ)OJ練習(xí)+帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問。

一.leetcode劍指 Offer II 027.?回文鏈表

1.問題描述

2.問題分析與求解

(1) 快慢指針法定位鏈表的中間節(jié)點(diǎn)

(2)?將鏈表后半部分進(jìn)行反轉(zhuǎn)

附:遞歸法反轉(zhuǎn)鏈表

(3)?雙指針法判斷鏈表是否回文

二.帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)

1.頭文件

2.節(jié)點(diǎn)內(nèi)存申請(qǐng)接口和鏈表初始化接口

3.鏈表的打印和查找接口

4.鏈表的增刪接口

5.鏈表銷毀接口

一.leetcode劍指 Offer II 027.?回文鏈表

劍指 Offer II 027. 回文鏈表 - 力扣（Leetcode）

1.問題描述

給定一個(gè)鏈表的頭節(jié)點(diǎn)head,請(qǐng)判斷其是否為回文鏈表。(是回文鏈表則程序返回true,不是回文鏈表則程序返回false)

如果一個(gè)鏈表是回文,那么鏈表節(jié)點(diǎn)序列從前往后看和從后往前看是相同的

題解接口：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution 
{
public:
    bool isPalindrome(ListNode* head) 
    {

    }
};

2.問題分析與求解

如果要求題解的時(shí)間復(fù)雜度為O(N),空間復(fù)雜度為O(1),那么本題的求解要分為三個(gè)部分：

用快慢指針法找到鏈表中間位置節(jié)點(diǎn)

將鏈表后半部分進(jìn)行反轉(zhuǎn)

用雙指針法將鏈表前半部分和后半部分進(jìn)行比對(duì)來判斷鏈表是否回文

(1) 快慢指針法定位鏈表的中間節(jié)點(diǎn)

思路是兩個(gè)指針同時(shí)遍歷鏈表,快指針一次走兩步(fast=fast->next->next),慢指針一次走一步(slow = slow->next)。

當(dāng)快指針結(jié)束遍歷時(shí),慢指針恰好會(huì)指向中間位置的節(jié)點(diǎn)(對(duì)于奇數(shù)個(gè)節(jié)點(diǎn)的鏈表而言,慢指針最后會(huì)指向中間節(jié)點(diǎn),對(duì)于偶數(shù)個(gè)節(jié)點(diǎn)的鏈表而言,慢指針最后會(huì)指向中間兩個(gè)節(jié)點(diǎn)的第二個(gè)節(jié)點(diǎn))

尋找中間位置節(jié)點(diǎn)的接口：
    ListNode * FindMid(ListNode * head)
    {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next)   //注意循環(huán)的限制條件
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
我們以偶數(shù)個(gè)節(jié)點(diǎn)鏈表的情況為例,簡(jiǎn)單地證明一下慢指針最后會(huì)指向中間兩個(gè)節(jié)點(diǎn)的第二個(gè)節(jié)點(diǎn)：

對(duì)于奇數(shù)個(gè)節(jié)點(diǎn)鏈表的情況也可以作相似的證明。?

(2)?將鏈表后半部分進(jìn)行反轉(zhuǎn)

定位鏈表中間位置節(jié)點(diǎn)后,我們便可以將鏈表的后半部分進(jìn)行反轉(zhuǎn).

完成鏈表反轉(zhuǎn)的最優(yōu)方法是三指針反轉(zhuǎn)法(動(dòng)畫)：

三指針反轉(zhuǎn)鏈表

的接口：
    ListNode * reverse (ListNode * head)
    {
        ListNode * cur = (nullptr == head)? nullptr : head->next;
        ListNode * pre = head;
        while(cur)
        {
            ListNode* Next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = Next;
        }
        if(head)
        head->next = nullptr;   //記得將被反轉(zhuǎn)部分鏈表的尾結(jié)點(diǎn)的指針域置空
        return pre;             //pre最終指向反轉(zhuǎn)鏈表的表頭
    }

附:遞歸法反轉(zhuǎn)鏈表

遞歸算法經(jīng)常出現(xiàn)在單鏈表問題的題解中,其原因在于:遞歸算法可以利用多個(gè)函數(shù)棧幀來存儲(chǔ)每一個(gè)鏈表節(jié)點(diǎn)的地址(而單鏈表的缺陷正是在于尋址困難),所以遞歸算法經(jīng)常作為單鏈表問題的可行解之一.(但是遞歸算法由于壓棧開銷較大,往往并不是最優(yōu)解,比如遞歸法反轉(zhuǎn)鏈表在時(shí)間和空間上的開銷都要比三指針反轉(zhuǎn)法更大)

然而以思維訓(xùn)練和加深對(duì)遞歸的理解為目的,這里嘗試著解構(gòu)一下遞歸反轉(zhuǎn)單鏈表的算法。

反轉(zhuǎn)單鏈表遞歸函數(shù)的建立：

遞歸反向遍歷鏈表節(jié)點(diǎn)的框架：

    ListNode* reverseList (ListNode * head)
    {
        if(head->next == nullptr)//遞歸的結(jié)束條件
        {
            return head;
        }
        reverseList(head->next);
        return head;   
    }

該遞歸框架可以實(shí)現(xiàn)反向遍歷單鏈表(圖解) 數(shù)據(jù)結(jié)構(gòu):鏈表基礎(chǔ)OJ練習(xí)+帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)

在遞歸函數(shù)反向遍歷鏈表節(jié)點(diǎn)的過程中我們可以加入修改節(jié)點(diǎn)指針域的操作:?

    ListNode* reverseList (ListNode * head)
    {
        if(head->next == nullptr)//遞歸的結(jié)束條件
        {
            return head;
        }
        reverseList(head->next);
        head->next->next = head; 
        head->next = nullptr;
        return head;
    }

遞歸函數(shù)修改節(jié)點(diǎn)指針域過程動(dòng)畫解析：

數(shù)據(jù)結(jié)構(gòu):鏈表基礎(chǔ)OJ練習(xí)+帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)

我們希望函數(shù)能夠?qū)?span style="color:#fe2c24;">反轉(zhuǎn)后鏈表的新頭節(jié)點(diǎn)的地址作為最終返回值帶回：

    ListNode* reverseList (ListNode * head)
    {
        if(head->next == nullptr)//遞歸的結(jié)束條件
        {
            return head;
        }
        ListNode* newhead = reverseList(head->next); //利用newhead將新的頭節(jié)點(diǎn)地址逐層帶回
        head->next->next = head; 
        head->next = nullptr;
        return newhead;
    }

遞歸函數(shù)將新的頭節(jié)點(diǎn)地址逐層帶回的過程圖解: 數(shù)據(jù)結(jié)構(gòu):鏈表基礎(chǔ)OJ練習(xí)+帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)

遞歸反轉(zhuǎn)單鏈表的接口：

    ListNode* reverseList(ListNode* head) 
    {
        if(nullptr == head || nullptr == head->next)
        //設(shè)置遞歸的限制條件,構(gòu)建遞歸框架
        {
            return head;
        }
        ListNode * newhead = reverseList(head->next);
        //newhead是為了將新的頭節(jié)點(diǎn)地址逐層帶回到最外層遞歸函數(shù)作為返回值
        head->next->next = head;
        //從原尾結(jié)點(diǎn)開始實(shí)現(xiàn)反向鏈接
        head->next = nullptr;
        //這里逐層置空是為了最后將新的尾結(jié)點(diǎn)指針域置空
        return newhead;           
    }

由于遞歸算法開銷比較大,所以題解接口中我們采用三指針反轉(zhuǎn)法來完成鏈表的反轉(zhuǎn).?

(3)?雙指針法判斷鏈表是否回文

經(jīng)過前兩個(gè)步驟后,鏈表后半部分完成了反轉(zhuǎn): 數(shù)據(jù)結(jié)構(gòu):鏈表基礎(chǔ)OJ練習(xí)+帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)

最后在題解接口中用雙指針判斷鏈表是否回文即可：

數(shù)據(jù)結(jié)構(gòu):鏈表基礎(chǔ)OJ練習(xí)+帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)

題解代碼:?

class Solution 
{
public:
    ListNode * FindMid(ListNode * head)   //快慢指針法尋找鏈表中間位置節(jié)點(diǎn)的接口
    {
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast && fast->next)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;                       //返回鏈表中間位置節(jié)點(diǎn)
    }
    ListNode * reverse (ListNode * head)   //反轉(zhuǎn)鏈表的接口(三指針翻轉(zhuǎn)法)
    {
        ListNode * cur = (nullptr == head)? nullptr : head->next;
        ListNode * pre = head;
        while(cur)
        {
            ListNode* Next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = Next;
        }
        if(head)       
        head->next = nullptr;   //記得將被反轉(zhuǎn)部分鏈表的尾結(jié)點(diǎn)的指針域置空
        return pre;             //pre最終指向反轉(zhuǎn)鏈表的表頭
    }
    bool isPalindrome(ListNode* head) 
    {
        ListNode* mid = FindMid(head);
        ListNode * reversehead = reverse(mid);
        ListNode * tem = reversehead;
        while(reversehead)
        {
            if(reversehead->val != head->val)
            {
                return false;
            }
            reversehead = reversehead->next;
            head = head->next;
        }
        reverse(tem);             //恢復(fù)原鏈表
        return true;
    }
};

數(shù)據(jù)結(jié)構(gòu):鏈表基礎(chǔ)OJ練習(xí)+帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)

二.帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)

鏈表共有8個(gè)種類,然而在現(xiàn)實(shí)中大多情形下能派上用場(chǎng)的鏈表只有兩種:

無頭單向非循環(huán)鏈表:實(shí)際中無頭單向非循環(huán)鏈表常作為其他數(shù)據(jù)結(jié)構(gòu)的子結(jié)
構(gòu)，如哈希桶、圖的鄰接表等等

帶頭雙向循環(huán)鏈表:該種鏈表結(jié)構(gòu)是由設(shè)計(jì)C++STL的大神設(shè)計(jì)出來的,結(jié)構(gòu)優(yōu)良,使用和實(shí)現(xiàn)起來都比較方便(每個(gè)節(jié)點(diǎn)都有兩個(gè)指針域,比較耗空間)

每個(gè)帶頭雙向循環(huán)鏈表都有一個(gè)哨兵頭節(jié)點(diǎn),該節(jié)點(diǎn)不存儲(chǔ)有效數(shù)據(jù).

帶頭雙向循環(huán)鏈表的環(huán)狀示意圖:

1.頭文件

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

typedef int LTDataType;

typedef struct LTNode
{
    LTDataType val;
    struct LTNode* pre;           //指向前一個(gè)節(jié)點(diǎn)的指針
    struct LTNode* next;          //指向下一個(gè)節(jié)點(diǎn)的指針
}LTNode;


//各個(gè)鏈表操作接口的聲明
LTNode* BuyLTNode(LTDataType x);
void ListPrint(LTNode* phead);
LTNode* ListInit();
LTNode* ListFind(LTNode* phead, LTDataType x);

void ListInsert(LTNode* pos, LTDataType x);
void ListErase(LTNode* pos, LTNode* phead);
void ListPushFront(LTNode* phead, LTDataType x);
void ListPopFront(LTNode* phead);
void ListPopBack(LTNode* phead);
void ListPushBack(LTNode* phead, LTDataType x);
void ListDestory(LTNode* phead);

2.節(jié)點(diǎn)內(nèi)存申請(qǐng)接口和鏈表初始化接口

節(jié)點(diǎn)內(nèi)存申請(qǐng)接口：
LTNode* BuyLTNode(LTDataType x)  //向系統(tǒng)申請(qǐng)鏈表節(jié)點(diǎn)空間的接口
{
    LTNode* NewNode = (LTNode*)malloc(sizeof(LTNode));
    if (NULL == NewNode)
    {
        perror("malloc failed:");
        exit(-1);
    }
    NewNode->next = NULL;
    NewNode->pre = NULL;
    NewNode->val = x;
    return NewNode;
}
鏈表初始化接口:
LTNode* ListInit()    //鏈表初始化接口(鏈表初始化時(shí)創(chuàng)建哨兵節(jié)點(diǎn),接口返回哨兵節(jié)點(diǎn)的地址)
{
    LTNode* phead = BuyLTNode(-1);
    phead->next = phead;
    phead->pre = phead;
    return phead;
}
帶頭雙向循環(huán)鏈表的初始化就是申請(qǐng)一個(gè)哨兵節(jié)點(diǎn):

使用時(shí)在主函數(shù)中用一個(gè)LTNode類型的指針接收該哨兵節(jié)點(diǎn)的地址.比如：
int main ()
{
    phead = ListInit();

    // 其他鏈表操作

    return 0;
}

3.鏈表的打印和查找接口

帶頭雙向循環(huán)鏈表的遍歷過程是從哨兵節(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開始到哨兵節(jié)點(diǎn)前一個(gè)節(jié)點(diǎn)結(jié)束。

數(shù)據(jù)結(jié)構(gòu):鏈表基礎(chǔ)OJ練習(xí)+帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)

void ListPrint(LTNode* phead)     //打印鏈表接口(注意不要打印哨兵節(jié)點(diǎn)中的無效數(shù)據(jù))
{
    assert(phead);
    LTNode* tem = phead->next;
    while (tem != phead)
    {
        printf("%d ", tem->val);
        tem = tem->next;
    }
    printf("\n");
}
LTNode* ListFind(LTNode* phead, LTDataType x)  //根據(jù)節(jié)點(diǎn)中存儲(chǔ)的數(shù)據(jù)查找某個(gè)鏈表節(jié)點(diǎn)
{
    assert(phead);
    LTNode* tem = phead->next;
    while (tem != phead)
    {
        if (x == tem->val)
        {
            return tem;
        }
        tem = tem->next;
    }
    return NULL;
}

4.鏈表的增刪接口

刪除pos地址處節(jié)點(diǎn)的接口?

void ListErase(LTNode* pos, LTNode* phead)    //刪除pos位置的節(jié)點(diǎn)
{
    assert(pos && pos != phead);
    LTNode* Pre = pos->pre;
    LTNode* Next = pos->next;
    Pre->next = Next;
    Next->pre = Pre;
    free(pos);
    pos = NULL;
}

在pos地址節(jié)點(diǎn)的后一個(gè)位置插入一個(gè)節(jié)點(diǎn)的接口:

void ListInsert(LTNode* pos, LTDataType x)    //在pos位置后插入一個(gè)鏈表節(jié)點(diǎn)的接口
{
    assert(pos);
    LTNode* newnode = BuyLTNode(x);
    LTNode* Next = pos->next;

    pos->next = newnode;
    newnode->pre = pos;
    newnode->next = Next;
    Next->pre = newnode;
}

頭插,頭刪以及尾插尾刪接口通過復(fù)用上面的兩個(gè)接口即可實(shí)現(xiàn):?

void ListPushFront(LTNode* phead, LTDataType x) //頭插一個(gè)節(jié)點(diǎn)
{
    assert(phead);
    ListInsert(phead, x);
}
void ListPopFront(LTNode* phead)                //頭刪一個(gè)節(jié)點(diǎn)
{
    assert(phead && phead->next != phead);
    ListErase(phead->next, phead);
}
void ListPopBack(LTNode* phead)                 //尾刪一個(gè)節(jié)點(diǎn)
{
    assert(phead && phead->pre != phead);
    ListErase(phead->pre, phead);
}
void ListPushBack(LTNode* phead, LTDataType x)  //尾插一個(gè)節(jié)點(diǎn)
{
    assert(phead);
    ListInsert(phead->pre, x);
}

注意哨兵節(jié)點(diǎn)不允許在刪除數(shù)據(jù)操作中被刪除

5.鏈表銷毀接口

void ListDestory(LTNode* phead)                 //銷毀鏈表的接口
{
    assert(phead);
    LTNode* tem = phead->next;
    while (tem != phead)
    {
        LTNode* Next = tem->next;
        free(tem);
        tem = Next;
    }
    free(phead);
    phead = NULL;
}

?注意哨兵節(jié)點(diǎn)最后才銷毀

可以看見,帶頭雙向循環(huán)鏈表的各個(gè)操作接口的時(shí)間復(fù)雜度都是O(1),這點(diǎn)充分體現(xiàn)了其數(shù)據(jù)結(jié)構(gòu)的優(yōu)良性。?

? 數(shù)據(jù)結(jié)構(gòu):鏈表基礎(chǔ)OJ練習(xí)+帶頭雙向循環(huán)鏈表的實(shí)現(xiàn) 文章來源地址http://www.zghlxwxcb.cn/news/detail-434561.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu):鏈表基礎(chǔ)OJ練習(xí)+帶頭雙向循環(huán)鏈表的實(shí)現(xiàn)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！