快捷導(dǎo)航

C語(yǔ)言超詳細(xì)i講解雙向鏈表

更新時(shí)間：2022年05月26日 10:25:03 作者：披星戴月的賈維斯

在實(shí)際生活中，我們用到的最多的兩種鏈表結(jié)構(gòu)就是單鏈表和雙向帶頭鏈表，上一篇已經(jīng)介紹了單鏈表的實(shí)現(xiàn)以及一些應(yīng)用，接下來(lái)我為大家詳細(xì)介紹一下雙向鏈表，以及一些鏈表oj題

一、雙向鏈表的概念

1、概念：概念：雙向鏈表是每個(gè)結(jié)點(diǎn)除后繼指針外還有?個(gè)前驅(qū)指針。雙向鏈表也有帶頭結(jié)點(diǎn)結(jié)構(gòu)和不帶頭結(jié)點(diǎn)結(jié)構(gòu)兩種，帶頭結(jié)點(diǎn)的雙向鏈表更為常用；另外，雙向鏈表也可以有循環(huán)和非循環(huán)兩種結(jié)構(gòu)，循環(huán)結(jié)構(gòu)的雙向鏈表更為常用。

二、雙向鏈表的實(shí)現(xiàn)

頭文件List.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int LTDateType;
typedef struct ListNode
{
	LTDateType date;
	struct ListNode* next;
	struct ListNode* prev;
}LTNode;
//void ListInit(LTNode** pphead)；
void ListPrint(LTNode* phead);
void ListPopBack(LTNode* phead);
LTNode* ListInit();//初始化
LTNode* BuyLTNode(LTDateType x);
void ListPushBack(LTNode* phead, LTDateType x);
void ListPushFront(LTNode* phead, LTDateType x);
void ListPopFront(LTNode* phead);
LTNode* ListFind(LTNode* phead, LTDateType x);
//在pos前插入
void ListInsert(LTNode* pos, LTDateType x);
//刪除pos位置的節(jié)點(diǎn)
void ListErease(LTNode* pos);
void ListDestory(LTNode* phead);

源文件List.C

#include"List.h"
LTNode* BuyLTNode(LTDateType x)
{
	LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
	if (newnode == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}
	newnode->date = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
//void ListInit(LTNode** pphead)
//{
//	assert(pphead);
//	*pphead = BuyLTNode(0);
//	(*pphead)->next = *pphead;
//	(*pphead)->prev = *pphead;
//}
LTNode* ListInit()
{
	LTNode* phead = BuyLTNode(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
void ListPrint(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d ", cur->date);
		cur = cur->next;
	}
	printf("\n");
}
void ListPushBack(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* tail = phead->prev;
	LTNode* newnode = BuyLTNode(x);
	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
void ListPushFront(LTNode* phead, LTDateType x)
{
	assert(phead);
	ListInsert(phead->next, x);
}
void ListPopBack(LTNode* phead)//尾刪
{
	assert(phead);
	assert(phead->next != phead);//說(shuō)明傳進(jìn)來(lái)的不只有phead,不然phead被free掉了。
	//LTNode* tail = phead->prev;
	//LTNode* tailPrev = tail->prev;
	//free(tail);
	//tail = NULL;
	//tailPrev->next = phead;
	//phead->prev = tailPrev;
	ListErease(phead->prev);
}
void ListPopFront(LTNode* phead)//頭刪
{
	assert(phead);
	assert(phead->next != phead);
	ListErease(phead->next);
}
LTNode* ListFind(LTNode* phead, LTDateType x)
{
	assert(phead);
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->date == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
//void ListInsert(LTNode* pos, LTDateType x)
//{
//	assert(pos);
//	LTNode* newnode = BuyLTNode(x);
//	pos->prev->next = newnode;
//	newnode->prev = pos->prev;
//
//	pos->prev = newnode;
//	newnode->next = pos;
//
//}
//更好的寫(xiě)法
void ListInsert(LTNode* pos, LTDateType x)
{
	assert(pos);
	//無(wú)關(guān)寫(xiě)的順序
	LTNode* newnode = BuyLTNode(x);
	LTNode* posPrev = pos->prev;
	newnode->next = pos;
	pos->prev = newnode;
	posPrev->next = newnode;
	newnode->prev = posPrev;
}
// 駝峰法
//函數(shù)和類(lèi)型所以單詞首字母大寫(xiě)
//變量：第一個(gè)單詞小寫(xiě)后續(xù)單詞首字母大寫(xiě)
void ListErease(LTNode* pos)
{
	assert(pos);
	LTNode* prev = pos->prev;
	LTNode* next = pos->next;
	free(pos);
	//此時(shí)要把pos置成空，不然pos就是野指針了
	pos = NULL;
	prev->next = next;//LT的新的prev指向pos->next;
	next->prev = prev;//LT的新的next的prev指向prev;
}
void ListDestory(LTNode* phead)
{
	assert(phead);
	LTNode* cur = phead->next;//從頭結(jié)點(diǎn)的下一個(gè)位置開(kāi)始。
	while (cur != phead)
	{
		LTNode* next = cur->next;//先記錄，再free
		//ListErease(cur);//副用Erease函數(shù)實(shí)現(xiàn)destory
		free(cur);//
		cur = next;
	}
	free(phead);
	//phead = NULL;形參的改變不影響實(shí)參
}

三、鏈表與順序表的差別

不同點(diǎn)	順序表	鏈表
存儲(chǔ)空間上	物理上一定連續(xù)	邏輯上連續(xù)，但物理上不一定連續(xù)
隨機(jī)訪問(wèn)	支持O(1)	不支持：O(N）
任意位置插入或者刪除元素	可能需要搬移元素，效率低O(N)	只需修改指針指向
插入	動(dòng)態(tài)順序表，空間不夠時(shí)需要擴(kuò)容	沒(méi)有容量的概念
應(yīng)用場(chǎng)景	元素高效存儲(chǔ)+頻繁訪問(wèn)	任意位置插入和刪除頻繁
緩存利用率	高	低

四、鏈表oj

1、鏈表中倒數(shù)第k個(gè)結(jié)點(diǎn)_?？皖}霸_?？途W(wǎng)（鏈接）

思路：快慢指針?lè)ǎ琭ast先走k步， slow和fast同時(shí)走， fast走到尾時(shí)，slow就是倒數(shù)第k個(gè)

代碼示例：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    struct ListNode* slow, *fast;
    slow = fast = pListHead;
    while(k --)//走k步
    {
        //判斷K是否大于鏈表的長(zhǎng)度。
        if(fast == NULL) return NULL;
        fast = fast->next;
    }
    while(fast)//當(dāng)fast 指針走到尾時(shí)
    {
        slow = slow->next;
        fast = fast->next;
    }
    return slow;
}
第二種寫(xiě)法：
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k )
{
    struct ListNode* p1 = NULL, *p2 = NULL;
    p1 = pListHead;
    p2 = pListHead;
    int a = k;
    int c = 0;//記錄節(jié)點(diǎn)個(gè)數(shù)
      //p1指針先跑，并且記錄節(jié)點(diǎn)數(shù)，當(dāng)p1指針跑了k-1個(gè)節(jié)點(diǎn)后，p2指針開(kāi)始跑，
        //當(dāng)p1指針跑到最后時(shí)，p2所指指針就是倒數(shù)第k個(gè)節(jié)點(diǎn)
    while(p1)//當(dāng)p1 不為空時(shí)
    {
        p1 = p1->next;
        c ++;//節(jié)點(diǎn)個(gè)數(shù)增加
        if(k < 1) p2 = p2->next;
        k --;    
    }
    if(c < a) return NULL;
    return p2;
}

2、21. 合并兩個(gè)有序鏈表（鏈接）

思路：歸并的思想，將小的值尾插到新鏈表。時(shí)間復(fù)雜度為n^2;如果再定義一個(gè)尾指針，每次記錄尾。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    if(list1 == NULL)//list1和list2分別是兩個(gè)鏈表的頭指針
        return list2;
    if(list2 == NULL)
        return list1;
    struct ListNode* head = NULL, *tail = NULL;//head是新鏈表的頭指針，tail是新鏈表的尾指針
    while(list1 && list2)
    {
            if(list1->val < list2->val)
            {
                if(tail == NULL)//這一步不太理解
                {
                    head = tail = list1;
                }
                else
                {
                    tail->next = list1;//先傳指針指向
                    tail = list1;//再把list 的地址傳給tail，相當(dāng)于tail往前挪了一步。
                }
                list1 = list1->next;
            }
            else
            {
                if(tail == NULL)
                {
                    head = tail = list2;
                }
                else
                {
                    tail->next = list2;
                    tail = list2;//傳地址
                }
                 list2 = list2->next;
            }
    }
    if(list1)
    {
        tail->next = list1;//如果鏈表1不為空，而此時(shí)鏈表二為空，則直接把鏈表二的值連接過(guò)去就好了。
    }
    if(list2)
    {
        tail->next = list2;
    }
    return head;
}
//方法二：設(shè)置一個(gè)哨兵位頭結(jié)點(diǎn)
//head存隨機(jī)值， head->next存第一個(gè)鏈表的值。起到簡(jiǎn)化代碼的作用。
//一般的鏈表沒(méi)有設(shè)置哨兵位頭結(jié)點(diǎn)。
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
    struct ListNode* head = NULL, *tail = NULL;
    head = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    head->next = NULL;
    while(list1 && list2)
    {
            if(list1->val < list2->val)
            {
                    tail->next = list1;//先傳指針指向
                    tail = list1;//再把list 的地址傳給tail，相當(dāng)于tail往前挪了一步。
                list1 = list1->next;
            }
            else
            {
                    tail->next = list2;
                    tail = list2;//傳地址
                    list2 = list2->next;
            }
    }
    if(list1)
    {
        tail->next = list1;//如果鏈表1不為空，而此時(shí)鏈表二為空，則直接把鏈表二的值連接過(guò)去就好了。
    }
    if(list2)
    {
        tail->next = list2;
    }
    //解決內(nèi)存泄漏問(wèn)題；
    struct ListNode* list = head->next;
    free(head);
    return list;
}

3、鏈表分割_?？皖}霸_牛客網(wǎng)（鏈接）

思路：新設(shè)置兩個(gè)鏈表，小于x的插到第一個(gè)鏈表，大于x的插到第二個(gè)鏈表。

定義四個(gè)指針：LessHead, LessTail,GreatHead, GreatTail.

原鏈表的值分別尾插到這兩個(gè)鏈表，然后分別更新LessTail,和GreatTail;

最后LessTail的指針再指向GreatHead。完成兩個(gè)鏈表的連接。

想極端場(chǎng)景：

1、所有值比x小

2、所有值比x大

3、比x大和小都有，最后一個(gè)值是比x小

4、比x大和小都有，最后一個(gè)值是比x大

//構(gòu)成環(huán)鏈表，造成死循環(huán)。
//設(shè)置哨兵位
class Partition {
  public:
    ListNode* partition(ListNode* pHead, int x) {
        struct ListNode* lessHead, *lessTail, *greatHead, *greatTail;
        lessHead = lessTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        greatHead = greatTail = (struct ListNode*)malloc(sizeof(struct ListNode));
        lessTail->next = greatTail->next = NULL;
        struct ListNode* cur = pHead;
        while (cur) {
            if (cur->val < x) {
                lessTail->next = cur;
                lessTail = lessTail->next;
            } else {
                greatTail->next = cur;
                greatTail = greatTail->next;
            }
            cur = cur->next;
        }
        //完成鏈接工作
        lessTail->next = greatHead->next;
        greatTail->next = NULL;//切斷greetTail的最后與greetHead的鏈接
        struct ListNode* list = lessHead->next;
        free(lessHead);
        free(greatHead);
        return list;
    }
};

4、鏈表的回文結(jié)構(gòu)_?？皖}霸_?？途W(wǎng)（鏈接）

思路：找出鏈表的中間節(jié)點(diǎn)，然后逆置，判斷前后鏈表是否一致，若一致，則說(shuō)明該鏈表是回文結(jié)構(gòu)。

為什么奇數(shù)個(gè)時(shí)也能過(guò)，

例如：1 2 3 2 1

逆置完變?yōu)榱?1 2 1 2 3 ；

當(dāng)A走到2的位置時(shí)2->next = 3, rHead走到的 2->next = 3，相等。

class PalindromeList {
public:
    struct ListNode* middleNode(struct ListNode* head)
{
    struct ListNode* slow, * fast;
    slow = fast = head;
    while(fast && fast->next) //想的是結(jié)束的條件，寫(xiě)的是繼續(xù)的條件
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}
    struct ListNode* reverseList(struct ListNode* head)
{
    struct ListNode* NewHead = NULL;
    struct ListNode* cur = head;
    while(cur)
    {
        struct ListNode* next = cur->next;
        //頭插
        cur->next = NewHead;//更多代表鏈表的指向方向。
        NewHead = cur;//接著把地址傳過(guò)來(lái)(更新)
        cur = next;//（更新）
    }
    return NewHead;
    }
    bool chkPalindrome(ListNode* A) {
        struct ListNode* mid = middleNode(A);
        struct ListNode*rHead = reverseList(mid);//應(yīng)該逆置mid，中間結(jié)點(diǎn)。
        while(A && rHead)
        {
            if(A->val == rHead->val)
            {
                A = A->next;
                rHead = rHead->next;
            }
            else
            {
                return false;
            }
        }
        return true;
    }
};

5、力扣相交鏈表（鏈接）

思路1：A鏈表每個(gè)節(jié)點(diǎn)B跟鏈表依次比較，如果有相等，就是相交，第一個(gè)相等就是交點(diǎn)。

時(shí)間復(fù)雜度：o(N*M);

思路二：如果兩個(gè)鏈表相交，則這兩個(gè)鏈表的最后一個(gè)元素的地址相同。

包含思路二三：

代碼示例：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode* tailA, *tailB;//因?yàn)橹筮€要用到headA,和headB,所以要用tail來(lái)進(jìn)行迭代。
    tailA = headA, tailB = headB;
    int lenA = 1, lenB = 1;
    while(tailA)//求出A的尾
    {
        tailA = tailA->next;
        ++lenA;//求出A的長(zhǎng)度
    }   
    while(tailB)//求出鏈表B的尾
    {
        tailB = tailB->next;
        ++lenB;//求出B的長(zhǎng)度
    }
    if(tailA != tailB)//如果兩個(gè)鏈表的尾不相等，則返回空
    {
        return NULL;
    }
    //相交，求交點(diǎn)，長(zhǎng)的先走差距步，再同時(shí)找交點(diǎn)。
    struct ListNode* shortList = headA, *longList = headB;//默認(rèn)A短B長(zhǎng)
    if(lenA > lenB)
    {
        shortList = headB;
        longList = headA;
    }
    int gap = abs(lenA - lenB);//求出差距
    while(gap--)//減gap次，若是--gap,就是減了gap - 1次
    {
        longList = longList->next;
    }
    while(shortList && longList)
    {
        if(shortList == longList)
        return shortList;//此時(shí)shortList == longList;
        longList = longList->next;
        shortList = shortList->next;
    }
    //最最關(guān)鍵的一步：就是要在外面返回一個(gè)值，因?yàn)榫幾g器不會(huì)判斷代碼在哪返回，只會(huì)檢查你的代碼的語(yǔ)法問(wèn)題。
    return NULL;
}