一：鏈表是什么
1、鏈表是物理存儲單元上非連續的、非順序的存儲結構，數據元素的邏輯順序是通過鏈表的指針地址實現，有一系列結點（地址）組成，結點可動態的生成。
2、結點包括兩個部分：（1）存儲數據元素的數據域（內存空間），（2）存儲指向下一個結點地址的指針域。
3、相對于線性表順序結構，操作復雜。
4.鏈表分為 （1）單鏈表 （2）雙鏈表 （3）單向循環鏈表 （4）雙向循環鏈表
二：鏈表的作用
1、實現數據元素的存儲按一定順序儲存，允許在任意位置插入和刪除結點。
2、包括單向結點，雙向結點，循環接點
三：鏈表與數組的區別
說到鏈表那肯定要聊一下數組，為什么會出現鏈表呢？
（1）數組：使用一塊連續的內存空間地址去存放數據，但
例如：
int a[5]={1,2,3,4,5}。突然我想繼續加兩個數據進去，但是已經定義好的數組不能往后加，只能通過定義新的數組
int b[7]={1,2,3,4,5,6,7}; ***********這樣就相當不方便比較浪費內存資源,對數據的增刪不好操作。
（2）鏈表：使用多個不連續的內存空間去存儲數據， 可以 節省內存資源（只有需要存儲數據時，才去劃分新的空間），對數據的增刪比較方便。
四、鏈表的優缺
優點:
(1)插入和刪除速度快，保留原有的物理順序，在插入或者刪除一個元素的時候，只需要改變指針指向即可。(2)沒有空間限制,存儲元素無上限,只與內存空間大小有關。(3)動態分配內存空間，不用事先開辟內存
缺點：
(1)占用額外的空間以存儲指針，比較浪費空間，不連續存儲，malloc函數開辟空間碎片比較多) (2) 查找速度比較慢，因為在查找時，只能順序查找，需要循環鏈表
五、關于頭指針，頭節點，首元節點的那些事
頭指針：指向鏈表第一個節點的指針（不一定是頭節點，因為……鏈表要是沒有頭節點呢？），沒有實際開辟空間 （即沒有用malloc等動態分配內存） 而且必須存在，因為頭指針不存在，就不便于對鏈表進行操作。
頭節點：不是必須存在（若存在則為鏈表的第一個節點）其主要作用是使所有鏈表（包括空表）的頭指針非空，并使對單鏈表的插入、刪除操作不需要區分是否為空表或是否在第一個位置進行（還是挺有用的）。其數據域可以不儲存任何數據，若儲存則通常是鏈表的長度啥的。
首元節點：第一個數據域中儲存有效數據的節點 若頭節點不存在 則其為鏈表的第一個節點，是一定要存在的（除非是空表）
有關鏈表的一些操作
1.單鏈表
節點結構默認為：
struct ListNode
{
int val;
struct ListNode *next;
}
①單鏈表的創建
//創建鏈表
struct ListNode* createList()
{
struct ListNode*p=NULL,*tail=NULL,*head=NULL;//p為待開辟的節點指針,tail為指向鏈表尾部的指針,head為指向鏈表頭部的指針。
//筆者喜歡在創建鏈表時 創建head tail 兩個指針 雖然不一定都用得到
int num; //將指針置空是個好習慣
scanf("%d",&num);
//尾插法 順序插法
while(num!=-1)//假設以num/val值為-1作為鏈表的結束標志 或者你用定長條件也行
{
p=(struct ListNode*)malloc(sizeof(struct ListNode));//注意此處用sizeof計算大小時在ListNode前要加struct關鍵字
p->val=num;
p->next=NULL;
if(head==NULL)//第一次循環時將頭指針head指向p
{
head=p;
}
else
{
tail->next=p;
}
tail=p;//此句放else里面也行 筆者更喜歡在第一次循環時就將tail與p與head產生關聯
scanf("%d",&num);
}
// 頭插法 逆序插法
// while(num!=-1)
// {
// p=(struct ListNode*)malloc(sizeof(struct ListNode));
// p->val=num;
// if(head==NULL)
// {
// head=p;
// }
// else
// {
// p->next=head;
// head=p;
// }
// }
tail->next=NULL//用p->next也行 這是尾插法
return head;//返回鏈表頭指針
}
②鏈表節點的插入
struct ListNode *insertList(ListNode *head,int index,int num)//index 表示在鏈表中插入的位置（從1開始）原位置的元素接在其后 num表示要插入的數值
{
struct ListNode *p=NULL,q;//在此q為虛擬節點 主要方便對鏈表進行操作
int cnt=1;//計數器從1開始計數
if(head==NULL&&head->next==NULL)//鏈表為空 返回一個空指針
return NULL;
if(index==1)//若插在頭結點(在此特指鏈表的第一個節點)的位置
{
p=(struct ListNode*)malloc(sizeof(struct ListNode));//給p開辟實際空間 用來儲存操作存入的值
p->val=num;
p->next=head;
head=p;
}
else
{
q=head;
while(q->next!=NULL&&cnt<=index)//對于鏈表我們通常對當前節點的下一個節點進行操作
{
if(cnt+1<index)//為什么要加一呢？因為表示下一個位置
{
q=q->next;
}
else
{
p=(struct ListNode *)malloc(sizeof(struct ListNode));
p->val=num;
p->next=q->next;
q->next=q;
}
}
}
if(cnt<index)//如果cnt還是 小于 index 則表明插在鏈表末尾
{
p=(struct ListNode*)malloc(sizeof(struct ListNode));
p->val=num;
p->next=NULL;
q->next=p;
}
return head;
}
③鏈表節點的刪除
struct ListNode *deleteList(struct ListNode *head,int num)//執行刪除節點val值為num的操作
{
struct ListNode *p=NULL,*q=NULL;//p，q均為輔助指針 不給他們開辟實際空間
if(head->val==num)//若刪除節點為頭結點
{
p=head;
head=head->next;
free(p);
}
else//若刪除節點為除頭結點外的其他節點
{
p=head;
while(p->next!=NULL)
{
if(p->next->val==num)
{
q=p->next;
p->next=p->next->next;
free(q);
}
else
{
p=p->next;
}
}
}
return head;
}
鏈表的遍歷
void printList(struct ListNode *head)
{
struct ListNode *p=head;//p依然為輔助指針
while(p!=NULL)//因為是遍歷（打印輸出）操作 所以對當前節點進行操作即可
{
printf("%d",p->val);
p=p->next;
}
}
雙向鏈表
雙向鏈表即單鏈表由單向的鏈變成了雙向的鏈（一個指針域(next)變成一前一后兩個指針域(prev,next)） 這里只演示雙向鏈表的創建
另：
節點結構為：
struct ListNode
{
int val;
ListNode *prev;
ListNode *next;
};
雙向鏈表的創建
struct ListNode *createDbList()
{
struct ListNode*p=NULL,*head=NULL,*tail=NULL;
int num;
scanf("%d",&num);
while(num!=-1)//以-1作為創建鏈表結束的標志
{
p=(struct ListNode*)malloc(sizeof(struct ListNode));
p->val=num;
if(head==NULL)//這里主要演示尾插法
{
head=p;
p->prev=NULL; //就不將雙向鏈表和循環鏈表相互摻和了
}
else
{
tail->next=p;
p->prev=tail;
}
tail=p;
}
tail->next=NULL;
}
循環鏈表
即將鏈表首尾相接 同樣這里只演示循環鏈表的創建
struct ListNode *createList()
{
struct ListNode*p,*head,*tail;
int num;
scanf("%d",&num);
while(num!=-1)
{
p=(struct ListNode*)malloc(sizeof(struct ListNode));
p->val=num;
if(head==NULL)
{
head=p;
}
else
{
tail->next=p;
}
tail=p;
}
tail->next=head;//創建結束后將鏈表首尾相接
}
靜態鏈表
靜態鏈表的節點通常用結構體數組表示
struct staticListNode
{
int val;
int cur;//游標cur用來儲存后繼節點的下標
};
1.Floyd判圈法：判斷鏈表是否有環（快慢指針的應用）
對于鏈表找環路的問題，有一個通用的解法——快慢指針(Floyd) 。給定兩個指針， 分別命名為 slow 和 fast ，起始位置在鏈表的開頭。每次 fast 前進兩步， slow 前進一步。如果 fast 可以走到盡頭，那么說明沒有環路；如果fast 可以無限走下去，那么說明一定有環路，且一定存 在一個時刻 slow 和 fast 相遇。當 slow 和 fast 第一次相遇時，我們將 fast 重新移動到鏈表開頭，并 讓 slow 和 fast 每次都前進一步。當 slow 和 fast 第二次相遇時，相遇的節點即為環路的開始點。
2. 判斷兩個鏈表是否相交
假設鏈表 A 的頭節點到相交點的距離是 a，鏈表 B 的頭節點到相交點的距離是 b，相交點到鏈表終點的距離為 c。我們使用兩個指針，分別指向兩個鏈表的頭節點，并以相同的速度前進，若到達鏈表結尾，則移動到另一條鏈表的頭節點繼續前進。按照這種前進方法，兩個指針會在a + b + c 次前進后同時到達相交節點
————————————————
版權聲明：本文為CSDN博主「legendarykk」的原創文章，遵循CC 4.0 BY-SA版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.NET/legendarykk/article/details/125592024
