大家好,我是melo,一名大二上軟體工程在讀生,經歷了一年的摸滾,現在已經在作業室里邊準備開發后臺專案啦
不過這篇文章呢,還是想跟大家聊一聊資料結構與演算法,學校也是大二上才開設了資料結構這門課,希望可以一邊學習資料結構一邊積累后臺專案開發經驗
寫在前邊
相信很多小猿人在初入資料結構的時候，或者說是在學習c語言的后期時分，總會遇到一個饞（纏）人的繞來繞去的家伙--就是我們今天要講的鏈表，為什么說鏈表纏人呢，鏈表的分類，題型的多樣性，鏈表的用途等等都是很多的，限于篇幅本篇著重來討論一下學習鏈表以及做題時的思路概覽,注意點以及有哪些小技巧
另外,本博客題解一般會使用c(學校課內要求)和java(個人后臺方向需要熟練應用)兩種語言
ps：本博客旨在提供一些學習和做題時的小技巧，推薦搭配資料結構演算法書籍一同學習和補充知識點
入門的話比較推薦的有《啊哈！演算法》，《大話資料結構》，這兩本書都偏向圖文式教學，也有很多可可愛愛的插畫
小哈確實好可愛啊哈哈哈
- 關于鏈表的定義，優點相信你們也都在書中看了蠻多了，這里就不多加闡述，我們直接來看形形色色的各種鏈表，看他們的區別和實作
鏈表的分類
我們先來看看最簡單的單向鏈表
- 鏈表是有序的串列，但是它在記憶體中是這樣存盤的
1)鏈表是以節點的方式來存盤,是鏈式存盤
2)每個節點包含data域，next域：指向下一個節點.
3)如圖：發現鏈表的各個節點不一定是連續存盤.
4)鏈表分帶頭節點的鏈表和沒有頭節點的鏈表，根據實際的需求來確定
帶頭結點邏輯結構示意圖如下
head中不存盤實際的資料data，只是用next來指向真正帶有資料的第一個節點
不帶頭結點
第一個節點即存盤有實際資料data和next的實際節點
何時要頭結點何時不需要呢
- 有無頭結點的區別在于，鏈表的第一個節點是否存盤值，那我們可以先大概下個定義：如果說我們的操作會影響到第一個節點的(比如說洗掉鏈表中的某個值)，那是不是我們盡量就用帶頭結點的會好一點
例如：洗掉結點時，如果我們不帶頭結點的話，如果洗掉的是第一個實際節點，那我們還需要去更改頭結點，讓頭結點指向第二個實際節點(因為第一個實際節點已經被洗掉了，自然就不是頭結點了)
而帶有頭結點的話，恰好就能解決這種需要特判的情況
這個區別，還需要我們慢慢去體會，在下文講到鏈表洗掉的時候自然而然就會更加深刻體會到了，這里只是先點一下，而到了后邊環形鏈表的時候，更多的是沒帶頭結點的版本
Typedef(偷懶神器)
- PNODE就等價于 struct Node* 了!
LinkList就直接等價于struct LNode*，可以省去很多書寫，下文中也會體現到
創建鏈表
思路概覽
- 我們需要兩個結點，一個指向當前節點，一個指向我們新創建的節點，每次創建新節點后，讓當前節點指向新節點，并移動當前節點到新節點上
記得最后跳出回圈的時候，要讓當前節點指向null來結束鏈表！
流程
鏈表節點定義(typedef妙用,后續可以省去struct)
#include<cstdio>
#include <malloc.h>
typedef struct ListNode {
int val;
struct ListNode* next;
};
注意c語言需要修改頭檔案中的cstido為stdio.h
注意讓當前pNow=head
可以省去特判i=0
//根據讀取的元素創建鏈表
ListNode* creatLinkedList() {
ListNode* head = (ListNode*)malloc(sizeof(ListNode));
ListNode* pNow = head;
int n,temp;
scanf("%d", &n);
for (int i = 0; i < n; i++) {
ListNode* pNew = (ListNode*)malloc(sizeof(ListNode));
scanf("%d", &(pNew->val));
//若是第一個
/*if (i == 0) {
head->next = pNew;
}*/
//將當前節點指向新節點,并移動當前節點到新節點上
pNow->next = pNew;
pNow = pNew;
}
//跳出回圈后,使得當前節點指向null終止鏈表
pNow->next = NULL;
return head;
}
特判第一個多一步 head->next=pNew
其實可以不用，在不帶頭結點的鏈表創建中，才需要去特判頭結點
記住最后跳出回圈讓pNow->next=null
遍歷鏈表
- 注意讓p=head->next，然后遍歷p（p=p->next）判斷 p !=null 即可
//遍歷鏈表
void traverseLinkedList(ListNode* head) {
for (ListNode* p = head->next; p != NULL; p=p->next) {
printf("%d ", p->val);
}
}
鏈表插入
在指定位置插入
思路概覽
- 首先我們第一感覺就是邀先移動到指定位置的前一位p，然后去新開辟一個節點pNew，讓p指向pNew，pNew指向原來p的下一節點
問題
- 如果我們原原本本按照思路來，有沒有發現，其實讓pNew指向原來p的下一節點，但是此時p的下一節點是什么呢，其實已經是pNew了
所以我們應該先用另一個指標，存盤一下原來p都下一個節點
或者說注意一下順序，先讓pNew的next=p的next
然后再讓p都next=pNew
注意
**校驗合法性
- 用while 和if 兩個條件剛好相反 可以省去獲取鏈表長度的操作
//鏈表插入(三種情況都綜合成一種)
bool insertLinkedList(ListNode* head, int position, int data) {
int i = 0;
ListNode* p = head;
ListNode* pNew = (ListNode*)malloc(sizeof(ListNode));
//移動p直到目標位置的前一位,條件是p不為null
while (i < position - 1 && p!=NULL) {
i++;
p = p->next;
}
//若移動不到,回傳false
if (i != position - 1 || p==NULL) {
return false;
}
pNew->val = data;
//注意順序
//先讓新節點指向上一個節點的下一節點
//然后再讓上一個節點指向新節點
pNew->next = p->next;
p->next = pNew;
return true;
}
鏈表洗掉
(力扣)203移除鏈表元素(洗掉所有滿足指定值的節點)
思路概覽
- 我們需要定義兩個指標，一個last記錄前一個節點，一個記錄當前節點now，怎么洗掉呢？讓last(圖中的p)->next=now(圖中的q)->next就可以了
***遞回還未看
https://leetcode-cn.com/problems/remove-linked-list-elements/
特判頭指標法
struct ListNode* removeElements(struct ListNode* head, int val){
//前指標
struct ListNode* last=head;
//當前指標
struct ListNode* now=head;
//now肯定要移動,而last就不一定要移動了!!!(此處注意)
for(;now!=NULL;now=now->next){
if(now->val==val){
//特判洗掉頭節點
if(now==head){
head=now->next;
}
//一般情況
else{
last->next=now->next;
}
}
//不刪,則移動last,若刪了就不用移動!!!
else{
last=now;
}
}
return head;
}
注意last需不需要移動!!!,且last默認先給頭節點
虛擬頭結點法(注意最后return)
struct ListNode_ dummyHead= (struct ListNode_)malloc(sizeof(struct ListNode));
struct ListNode* removeElements(struct ListNode* head, int val){
//創建虛擬頭節點,并指向第一個節點
struct ListNode* dummyHead= (struct ListNode*)malloc(sizeof(struct ListNode));
dummyHead->next=head;
//前指標
struct ListNode* last=dummyHead;
//當前指標
struct ListNode* now=head;
//now肯定要移動,而last就不一定要移動了!!!(此處注意)
for(;now!=NULL;now=now->next){
if(now->val==val){
//特判洗掉頭節點
last->next=now->next;
}
//不刪,則移動last,若刪了就不用移動!!!
else{
last=now;
}
}
return dummyHead->next;
}
(最優)while+虛擬頭
delete temp是c++中的，此處java會自動回收無需釋放空間
class Solution {
public ListNode removeElements(ListNode head, int val) {
//創建虛擬頭結點
ListNode dummyHead = new ListNode(0);
//讓虛擬頭結點指向給定的head結點
dummyHead.next = head;
//定義一個臨時結點來遍歷，默認從虛擬頭結點開始
ListNode temp = dummyHead;
while (temp.next != null) {
if (temp.next.val == val) {
//找到了則洗掉
temp.next = temp.next.next;
} else {
//找不到繼續移動
temp = temp.next;
}
}
return dummyHead.next;
}
}
**移除鏈表元素(指定位置)
題目
題解
#include "allinclude.h" //DO NOT edit this line
Status Delete_L(LinkList L, int i, ElemType &e)
{ // Add your code here
LNode* p = L;
int j=0;
//注意跟新增一個節點不一樣,此處得p->next!=NULL
while(j<i-1&&p->next!=NULL){
p=p->next;
j++;
}
//若引數不合法
if(j!=i-1||p->next==NULL){
return ERROR;
}
e= (p->next)->data;
//LNode* temp = p->next;
p->next = p->next->next;
//free(temp);
return OK;
}
**注意
- 跟新增一個節點不一樣,此處得p->next!=NULL,而不是p!=NULL
若是p!=NULL的話,下邊我們又要保存p->next,可能就非法訪問了!
*從第i元素起的所有元素從鏈表移除
題目
還記得上文的typedef嗎,此處定義了一個LinkList就等價于LNode*
相當于Typedef struct LNode LinkList*
題解
#include "allinclude.h" //DO NOT edit this line
Status Split_L(LinkList L, LinkList &Li, int i)
{ // Add your code here
int cnt=0;
LNode* p = L ;
LinkList temp;
//移動到前一位
while(cnt<i-1 && p->next!=NULL){
p=p->next;
cnt++;
}
//校驗引數合法性
if(cnt!=i-1||p->next==NULL){
Li=NULL;
return ERROR;
}
temp=(LinkList)malloc(sizeof(LNode));
if(temp==NULL) return ERROR;
Li=temp;
Li->next=p->next;
//銷毀i元素后
p->next=NULL;
return OK;
}
鏈表反轉
(力扣)206反轉鏈表
https://leetcode-cn.com/problems/reverse-linked-list/
思路概覽
- 讓后一個指向前一個，同時要記得要用另外一個指標保存下一個節點位置用于正常遍歷，總共需要三個指標
官方題解(迭代+三指標)
c語言
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* prev = NULL;
struct ListNode* curr = head;
while (curr) {
//先記錄curr的下一位,后續才能修改curr的下一位(總結就是要修改哪個值,就先保存下來)
struct ListNode* next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
java版
區別就在于java沒有指標而是參考,直接ListNode就好,沒有那個*(寫法方便一些)
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
}
Tips
要改變什么值,就先用一個臨時值來存盤
鏈表反轉中,要改變next,又怕影響正常的遍歷,所以先用一個臨時指標來存盤就好了,這樣就還能正常的遍歷下去
合并兩個有序鏈表
(力扣)21合并兩個有序鏈表
https://leetcode-cn.com/problems/merge-two-sorted-lists/
思路
- 同時遍歷兩個鏈表l1和l2，直到有一個為null
- 每次遍歷時，判斷是哪個比較小，然后加到新鏈表中，移動l1指標
直接if單獨比較版本
一次只能一個,但是就不用嵌套while(while還要再次判斷是不是空)
struct ListNode* mergeTwoLists2(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* drummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* Node = drummyHead;
while (l1 != NULL && l2 != NULL) {
if( l1->val <= l2->val) {
Node->next = l1;
l1 = l1->next;
}
else{
Node->next = l2;
l2 = l2->next;
}
Node = Node->next;
}
//最后出回圈必有一個為null(而且不會同時為null)則讓非空的剩余部分連上去即可
Node->next = l1 == NULL ? l2 : l1;
/*ListNode* p = drummyHead->next;
while (p) {
printf("%d", p->val);
p = p->next;
}*/
return drummyHead->next;
}
while中嵌套while版本
注意
內部while可能會破壞外部大while的條件,需要再次判斷
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* drummyHead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* Node = drummyHead;
while (l1 != NULL && l2 != NULL) {
while (l1 != NULL && l2 != NULL && l1->val <= l2->val) {
Node->next = l1;
Node = Node->next;
l1 = l1->next;
}
//可能l1已經為NULL了,所以也還得判斷l1
while (l2 != NULL && l1 != NULL && l2->val <= l1->val) {
Node->next = l2;
Node = Node->next;
l2 = l2->next;
}
}
//最后出回圈必有一個為null(而且不會同時為null)則讓非空的剩余部分連上去即可
Node->next = l1 == NULL ? l2 : l1;
/*ListNode* p = drummyHead->next;
while (p) {
printf("%d", p->val);
p = p->next;
}*/
return drummyHead->next;
}
總結
Tip
巧用typedef偷懶神器
有時候題目給的是不帶頭結點的,盡量自己去構造一個虛擬頭指標,可以省去一些特判的操作
要改變什么值,就先用一個臨時值來存盤
鏈表反轉中,要改變next,又怕影響正常的遍歷,所以先用一個臨時指標來存盤就好了,這樣就還能正常的遍歷下去
最后
- 有關其他鏈表知識,環形鏈表,約瑟夫等經典問題,melo最近比較忙,忙于學習多執行緒知識和接管一下專案,等到以后學校課程(小聲bb學校剛講到創建和遍歷鏈表)跟進了再后續補充,后續也會更新一些多執行緒的知識以及設計模式等內容,希望大家多多體諒和包涵
最近學校講到堆疊和佇列了,過段時間應該也會繼續更進完善堆疊和佇列相關的博客
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/298802.html
標籤：其他
上一篇：廣東 深圳 普通話測驗