鏈表結(jié)構(gòu)
鏈表是一種以不連續(xù)的方式存儲(chǔ)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)腰懂。對(duì)于最基本的單鏈表周叮，其每個(gè)節(jié)點(diǎn)不僅包含值val揩尸，也包含一個(gè)指向下一個(gè)節(jié)點(diǎn)地址的指針next。以C語言實(shí)現(xiàn)為例：
#include<stdio.h>
#include<stdlib.h>
struct ListNode
{
int val;
struct ListNode *next;
};
//判斷鏈表為空
int isEmpty(struct ListNode *head)
{
return head==NULL;
}
//查找節(jié)點(diǎn),找不到返回NULL
struct ListNode* find(int x, struct ListNode* head)
{
while(head && head->val!=x)
{
head=head->next;
}
return head;
}
//查找前驅(qū)節(jié)點(diǎn)
struct ListNode* findPrevious(int x, struct ListNode *head)
{
if(head->val==x)
{
return NULL;
}
struct ListNode* pre = head;
while(head && head->val!=x)
{
pre=head;
head=head->next;
}
return head==NULL?NULL:pre;
}
//插入節(jié)點(diǎn)
void insertNode(int x, struct ListNode*position)
{
struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
node->val=x;
struct ListNode *temp=position->next;
position->next=node;
node->next=temp;
}
//刪除節(jié)點(diǎn)
void deleteNode(int x, struct ListNode *head)
{
//頭刪
if(head->val==x)
{
struct ListNode *next = head->next;
free(head);
*head=*next;
}
struct ListNode *pre = findPrevious(x,head);
if(pre)
{
struct ListNode *cur = pre->next;
pre->next=cur->next;
free(cur);
}
}
void printList(struct ListNode *head)
{
int idx = 0;
while(head)
{
printf("%d --- element val is %d \n",idx,head->val);
head=head->next;
}
}
void main()
{
struct ListNode *dumpy = (struct ListNode *)malloc(sizeof(struct ListNode));
dumpy->val=1;
dumpy->next=NULL;
printList(dumpy);
printf("is empty ? %s \n",isEmpty(dumpy)?"yes":"no");
insertNode(2,find(1,dumpy));
printf("after insert :\n");
printList(dumpy);
deleteNode(2,dumpy);
printf("after delete :\n");
printList(dumpy);
}
注意：free()函數(shù)不會(huì)刪除指針，而是將指針指向的內(nèi)存釋放话肖。在刪除節(jié)點(diǎn)的函數(shù)中北秽，如果是頭刪，先獲得后一個(gè)節(jié)點(diǎn)最筒，即第二個(gè)節(jié)點(diǎn)贺氓，然后將頭指針指向的內(nèi)存釋放，再將頭指針指向第二個(gè)節(jié)點(diǎn)床蜘，*head=*next.
鏈表算法題
解決鏈表的問題辙培，一般可以有兩種方法：迭代和遞歸。
題一：反轉(zhuǎn)鏈表
核心思路：讓節(jié)點(diǎn)的next值指向上一個(gè)節(jié)點(diǎn)邢锯，這里需要同時(shí)保存當(dāng)前節(jié)點(diǎn)和前一個(gè)節(jié)點(diǎn)扬蕊，并同時(shí)移動(dòng)。
- 雙指針迭代法
遍歷每個(gè)節(jié)點(diǎn)丹擎，并將當(dāng)前節(jié)點(diǎn)的next指向上一個(gè)節(jié)點(diǎn)尾抑。這里需要定義指針變量pre保存前一個(gè)節(jié)點(diǎn)的指針，初始化為NULL(因?yàn)榉崔D(zhuǎn)后的尾節(jié)點(diǎn)就是反轉(zhuǎn)前的首節(jié)點(diǎn)蒂培。),并定義指針變量cur保存遍歷到的節(jié)點(diǎn)再愈。 當(dāng)遍歷完成時(shí)，pre保存的是原鏈表的尾節(jié)點(diǎn)护戳，也就是新鏈表的首節(jié)點(diǎn)翎冲。
//反轉(zhuǎn)鏈表
struct ListNode * reverseList(struct ListNode *head)
{
//如果鏈表為空或者只有一個(gè)節(jié)點(diǎn)，直接返回原鏈表
if(!head || !head->next)
{
return head;
}
struct ListNode *cur = head;
struct ListNode *pre = NULL;
while(head)
{
head=head->next;
cur->next=pre;
pre=cur;
cur=head;
}
return pre;
}
- 遞歸
遞歸函數(shù)的作用是讓節(jié)點(diǎn)的next指向上一節(jié)點(diǎn)媳荒。
//遞歸反轉(zhuǎn)
struct ListNode *reverseList2(struct ListNode *head)
{
if(!head || !head->next)
{
return head;
}
struct ListNode *temp = reverseList2(head->next);
head->next->next=head;
head->next=NULL;
return temp;
}
題二：合并連個(gè)有序鏈表
輸入兩個(gè)遞增排序的鏈表抗悍，合并這兩個(gè)鏈表并使新鏈表中的節(jié)點(diǎn)仍然是遞增排序的。
- 迭代法
定義一個(gè)新鏈表钳枕，一次比較兩個(gè)鏈表的值缴渊，取小的值加到新鏈表上，直到一個(gè)鏈表遍歷完畢么伯，將另一個(gè)鏈表的剩余部分加到新鏈表上疟暖。
//合并有序鏈表
struct ListNode *mergeList(struct ListNode * l1,struct ListNode* l2)
{
struct ListNode* l3 = (struct ListNode *)malloc(sizeof(struct ListNode));
struct ListNode* dumpy = l3;
while(l1 && l2)
{
if(l1->val<l2->val)
{
l3->next=l1;
l1=l1->next;
}
else
{
l3->next=l2;
l2=l2->next;
}
l3=l3->next;
}
l3->next=l1==NULL?l2:l1;
return dumpy->next;
}
- 遞歸
遞歸函數(shù)的作用是創(chuàng)建一個(gè)節(jié)點(diǎn)，依次比較兩個(gè)鏈表值田柔，取小的值作為新節(jié)點(diǎn)的值俐巴，next指向的值也是通過比較所得。
struct ListNode* mergeList2(struct ListNode* l1,struct ListNode* l2)
{
if(l1==NULL)
{
return l2;
}
if(l2==NULL)
{
return l1;
}
struct ListNode *node = (struct ListNode *)malloc(sizeof(struct ListNode));
if(l1->val<l2->val)
{
node->val=l1->val;
node->next=mergeList2(l1->next,l2);
}
else
{
node->val=l2->val;
node->next=mergeList2(l1,l2->next);
}
return node;
}
迭代法和遞歸法是處理鏈表問題的常見方法硬爆，迭代相對(duì)更好理解欣舵。
更多習(xí)題，詳見我的github
