【练习】链表及链表面试题（一）入门

巩固一下基础，我重新写了一下无头节点单链表及链表面试题。我会分为入门，基础，进阶三章进行总结，点击以下蓝色字直接跳转对应章节。

链表及链表面试题（一）入门
链表面试题（二）基础
链表面试题（三）进阶

** 首先看一下顺序表和链表的优缺点，分别在什么场景下使用？ **

• 顺序表存储
  ** 原理：** 顺序表存储是将数据元素放到一块连续的内存存储空间，存取效率高，速度快。但是不可以动态增加长度;
  ** 优点：** 存取速度高效，通过下标来直接存储;
  ** 缺点：** 1.插入和删除比较慢，2.不可以增长长度 ;
  比如：插入或者删除一个元素时，整个表需要遍历移动元素来重新排一次顺序;
• 链表存储
  ** 原理：** 链表存储是在程序运行过程中动态的分配空间，只要存储器还有空间，就不会发生存储溢出问题;
  ** 优点：** 插入和删除速度快，保留原有的物理顺序，比如：插入或者删除一个元素时，只需要改变指针指向即可;
  ** 缺点：** 查找速度慢，因为查找时，需要循环链表访问;

从它们的存储优缺点来看，各自有各自的** 使用场景 **,比如：频繁的查找却很少的插入和删除操作可以用顺序表存储，如果频繁的插入和删除操作很少的查询就可以使用链表存储;
查看原文

源代码：

list.h

//list.h

#ifndef __LIST_H__
#define __LIST_H__

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>

typedef int DataType;

typedef struct Node
{
    DataType data;
    struct Node* next;

}Node, *pNode, *pList;

//init list
void InitList(pList* pplist);
pNode BuyNode(DataType d);

//pop/push
void PushBack(pList* pplist, DataType d);
void PopBack(pList* pplist);
void PushFront(pList* pplist, DataType d);
void PopFront(pList* pplist);

int getsize(pList list);
void PrintList(pList plist);

pNode Find(pList plist, DataType d);
void Remove(pList* pplist, DataType d);
void RemoveAll(pList* pplist, DataType d);
void Insert(pList* pplist, pNode pos, DataType d);
void Erase(pList* pplist, pNode pos);

void ReverseList(pList* pplist);
void BubbleSort(pList* pplist);

void DestroyList(pList* pplist);

#endif // !__LIST_H__

• list.c

//list.c
#include "list.h"

void InitList(pList* pplist)
{
    assert(pplist);
    *pplist = NULL;
}

pNode BuyNode(DataType d)
{
    pNode pnode = (pNode)malloc(sizeof(Node));
    if (pnode == NULL)
    {
        perror("malloc error");
        return -1;
    }
    pnode->data = d;
    pnode->next = NULL;

    return pnode;
}

void PushBack(pList* pplist, DataType d)
{
    assert(pplist);
    pNode pNewNode = BuyNode(d);

    if (*pplist == NULL)//无节点case
    {
        *pplist = pNewNode;
    }
    else
    {
        pNode cur = *pplist;//指向当前节点指针
        while (cur->next != NULL)
        {
            cur = cur->next;
        }
        cur->next = pNewNode;
    }
}


void PopBack(pList* pplist)
{
    assert(pplist);
    
    pNode cur = *pplist;//指向当前节点指针

    if (cur == NULL)
    {
        return;
    }
    else if (cur->next == NULL) // 只有一个节点
    {
        free(cur);
        *pplist = NULL;
        return;
    }
    while (cur->next->next != NULL)//多个节点
    {
        cur = cur->next;
    }
    free(cur->next);
    cur->next = NULL;
}

void PushFront(pList* pplist, DataType d)
{
    pNode NewNode = BuyNode(d);
    assert(pplist);
    
    if (*pplist == NULL)
        *pplist = NewNode;
    else
    {
        NewNode->next = *pplist;
        *pplist = NewNode;
    }
}

void PopFront(pList* pplist)
{
    assert(pplist);
    pNode cur = *pplist;//指向当前节点指针
    if (cur == NULL)
        return;
    
    else if (cur->next == NULL)
    {
        free(cur);
        *pplist = NULL;
    }
    else
    {
        pNode tmp = *pplist;
        *pplist = cur->next;
        free(tmp);
    }
}

void PrintList(pList plist)
{
    pNode cur = NULL;
    if (plist == NULL)
    {
        printf("null\n");
        return;
    }
    cur = plist;
    printf("list: ");
    while (cur != NULL)
    {
        printf("%d --> ", cur->data);
        cur = cur->next;
    }
    printf("NULL\n");
}

pNode Find(pList plist, DataType d)
{
    pNode cur = plist;

    while (cur)
    {
        if (cur->data == d)
        {
            return cur;
        }
        cur = cur->next;
    }
    return NULL;
}

//删除指定元素
void Remove(pList* pplist, DataType d)
{
    assert(pplist);
    pNode cur = *pplist;
    
    while (cur)
    {
        if (cur->data == d)
        {
            if (cur == *pplist)
            {
                PopFront(pplist);
            }
            else if (cur->next == NULL)
            {
                PopBack(pplist);
            }
            else
            {
                pNode tmp = cur->next;
                cur->data = tmp->data;
                cur->next = tmp->next;
                free(tmp);
                tmp = NULL;
            }
            return;
        }
        
        cur = cur->next;
    }
    return;
}

//删除全部指定元素
void RemoveAll(pList* pplist, DataType d)
{
    pNode cur = *pplist;
    pNode pon = cur->next; //防止cur丢失
    while (cur)
    {
        if (cur->data == d)
        {
            if (cur == *pplist)
            {
                PopFront(pplist);
                cur = pon; //更新cur
            }
            else if (cur->next == NULL)
            {
                PopBack(pplist);
                cur = NULL;
                break;
            }
            else 
            {
                pNode tmp = cur->next;
                
                while (tmp->data == d)
                {
                    pNode last = tmp->next;
                    cur->next = tmp->next;
                    free(tmp);
                    tmp = last;
                }
                cur->data = tmp->data;
                cur->next = tmp->next;
                free(tmp);
                tmp = NULL;
            }
        }

        cur = cur->next;
    }
    return;
}

//随机位置插入
void Insert(pList* pplist, pNode pos, DataType d)
{
    pNode cur = *pplist;
    assert(pplist);
    if (cur == NULL)
    {
        PushBack(pplist, d);
        return;
    }
    if (pos == NULL)
    {
        return;
    }
    //方法1 swap
    /*pNode NewNode = BuyNode(d);
    DataType tmp = d;
    
    tmp = NewNode->data;
    NewNode->data = pos->data;
    pos->data = tmp;
    
    NewNode->next = pos->next;
    pos->next = NewNode;*/

    //方法2 
    pNode NewNode = BuyNode(pos->data);
    pos->data = d;
    NewNode->next = pos->next;
    pos->next = NewNode;
    
}

//指定位置删除
void Erase(pList* pplist, pNode pos)
{
    pNode cur = *pplist;
    pNode prev = NULL;

    assert(pplist);

    if (cur == NULL)
        return;
    else if (pos == NULL)
        return;
    
    else if (cur == pos)
    {
        PopFront(pplist);
        return;
    }
    while (cur != pos)
    {
        prev = cur;
        cur = cur->next;
    }
    prev->next = cur->next;
    free(cur);
    cur = NULL;
}

//逆置链表
void ReverseList(pList* pplist)
{
    assert(pplist);
    pNode cur = *pplist;
    pNode newhead = *pplist;

    if (cur == NULL || cur->next == NULL)
        return;
    

    while (cur->next)
    {
        pNode tmp = cur->next;
        cur->next = tmp->next;
        tmp->next = newhead;
        newhead = tmp;
    }   
    *pplist = newhead;
}

//getsize
int getsize(pList list)
{
    pNode cur = list;
    int size = 0;
    while (cur)
    {
        size++;
        cur = cur->next;
    }
    return size;
}

//冒泡排序
void BubbleSort(pList* pplist)
{
    assert(pplist);
    pNode p = NULL;
    pNode q = NULL;

    for (p = *pplist; p != NULL; p = p->next)
    {
        for (q = p->next; q != NULL; q = q->next)
        {
            if (p->data > q->data)
            {
                DataType tmp;
                tmp = p->data;
                p->data = q->data;
                q->data = tmp;
            }
        }
    }
}

void DestroyList(pList* pplist)
{
    pNode cur = *pplist;
    assert(pplist);
    while (cur != NULL)
    {
        pNode del = cur;
        cur = cur->next;
        free(del);
    }
    *pplist = NULL;
}

• test.c

//test.c

#include "list.h"

//pop/push/size
void test1()
{
    pList plist;
    InitList(&plist);

    //pushback/popback
    printf("\n test pushback\n");
    PushBack(&plist, 1);
    PushBack(&plist, 2);
    PushBack(&plist, 3);
    PrintList(plist);

int num = getsize(plist);
    printf("size: %d\n", num);

    printf("\n test popback\n");
    PopBack(&plist);
    PopBack(&plist);
    PopBack(&plist);
    PopBack(&plist);
    PrintList(plist);

    //pushfront/popfront
    printf("\n test pushfront\n");
    PushFront(&plist, 1);
    PushFront(&plist, 2);
    PushFront(&plist, 3);
    PrintList(plist);

    printf("\n test popfront\n");
    PopFront(&plist);
    PopFront(&plist);
    PopFront(&plist);
    PopFront(&plist);
    PrintList(plist);

    DestroyList(&plist);
}

//remove/removeall
void test2()
{
    pList plist;
    InitList(&plist);
    printf("\n");
    PushBack(&plist, 3);
    PushBack(&plist, 3);
    PushBack(&plist, 1);
    PushBack(&plist, 2);
    PushBack(&plist, 3);
    PushBack(&plist, 3);
    PushBack(&plist, 3);
    PushBack(&plist, 4);
    PushBack(&plist, 3);
    PushBack(&plist, 5);
    PrintList(plist);

    printf(" test remove\n");
    Remove(&plist, 3);
    Remove(&plist, 2);
    Remove(&plist, 5);
    Remove(&plist, 6);
    PrintList(plist);

    printf(" test removeall\n");
    RemoveAll(&plist, 3);
    PrintList(plist);
    RemoveAll(&plist, 3);
    PrintList(plist);

    DestroyList(&plist);
}

//find/insert/erase
void test3()
{
    pList plist;
    InitList(&plist);
    printf("\n");
    PushBack(&plist, 1);
    PushBack(&plist, 2);
    PushBack(&plist, 3);
    PushBack(&plist, 4);
    PushBack(&plist, 6);
    PushBack(&plist, 8);
    PrintList(plist);

    printf(" test insert\n");
    //中间
    pNode pos1 = Find(plist, 6);
    Insert(&plist, pos1, 5);
    //头部
    pNode pos2 = Find(plist, 1);
    Insert(&plist, pos2, 0);
    //尾部
    pNode pos3 = Find(plist, 8);
    Insert(&plist, pos3, 7);
    //节点不存在
    pNode pos4 = Find(plist, 10);
    Insert(&plist, pos4, 9);
    PrintList(plist);

    printf(" test erase\n");
    //中间
    pNode pos5 = Find(plist, 6);
    Erase(&plist, pos5);
    //头部
    pNode pos6 = Find(plist, 0);
    Erase(&plist, pos6);
    //尾部
    pNode pos7 = Find(plist, 8);
    Erase(&plist, pos7);
    //节点不存在
    pNode pos8 = Find(plist, 10);
    Erase(&plist, pos8);
    PrintList(plist);

    DestroyList(&plist);
}

//test_ReverseList
void test_ReverseList()
{
    pList plist;
    InitList(&plist);
    
    printf("\n");
    PushBack(&plist, 1);
    PushBack(&plist, 2);
    PushBack(&plist, 3);
    PushBack(&plist, 4);
    PushBack(&plist, 5);
    PushBack(&plist, 6);
    PrintList(plist);

    printf("test_ReverseList\n");
    ReverseList(&plist);
    PrintList(plist);

    DestroyList(&plist);
}

//test_BubbleSort
void test_BubbleSort()
{
    pList plist;
    InitList(&plist);
    
    printf("\n");
    PushBack(&plist, 3);
    PushBack(&plist, 6);
    PushBack(&plist, 5);
    PushBack(&plist, 8);
    PushBack(&plist, 1);
    PushBack(&plist, 4);
    PushBack(&plist, 7);
    PushBack(&plist, 2);
    PrintList(plist);
    
    printf("test_BubbleSort\n");
    BubbleSort(&plist);
    PrintList(plist);

    DestroyList(&plist);
}

int main()
{
    test1();
    test2();
    test3();
    test_ReverseList();
    test_BubbleSort();

    system("pause");
    return 0;
}

链表及链表面试题（一）入门
链表面试题（二）基础
链表面试题（三）进阶