鏈表結(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語(yǔ)言實(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)。

1. 雙指針迭代法

遍歷每個(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;
}

2. 遞歸

遞歸函數(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)仍然是遞增排序的。

1. 迭代法

定義一個(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;
}

2. 遞歸

遞歸函數(shù)的作用是創(chuàng)建一個(gè)節(jié)點(diǎn)，依次比較兩個(gè)鏈表值，取小的值作為新節(jié)點(diǎn)的值，next指向的值也是通過(guò)比較所得。

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