算法提升 （三）基础数据结构

作者：@小萌新
专栏：@算法提升
作者简介：大二学生 希望能够和大家一起进步！
内容简介：简单介绍基本数据结构的简单面试题

不负韶华

链表

阅读这篇文章之前需要有初阶数据结构的基础

关于链表的结构如果还有不了解的同学可以参考下我的这篇文章

链表的详细介绍

1. 反转单链表

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

这个题目在算法方面其实没有太多的技巧

主要是锻炼下我们的coding能力

我们来看图

单次的操作大概是这样子的

我们将当前的指针指向前面一个指针 这样子操作就完成啦

后面其实就是迭代操作

prev到pos位置

pos到next位置

next到最后的位置

代码表示如下

struct ListNode* reverseList(struct ListNode* head)
{
    if(head==NULL)
    {
        return NULL;
    }

    // 设置两个种子很 一个前指针一个后指针一个当前指针
    struct ListNode* prev =NULL;
    struct ListNode* pos =head;
    struct ListNode* next =head;


    while(pos)
    {
        next=next->next;
        pos->next = prev;
        prev = pos;
        pos =next;
    }

    return prev;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

没有什么难度

2. 反转双链表

给定双链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

这个的思路和前面反转单链表完全一致 按照上面的思路搞就可以

这里不再赘述

3. 删除链表中的重复项

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

我们先考虑一种特殊情况 当我们的头就是我们要删除的节点的时候是不是要用头删啊

并且这个时候还需要移动头的位置

直到我们当前的数据不是我们要删除的数据了 是不是头才能确定下来 大家想想看是不是

之后就很简单了

cur找重复项 prev记录前面的值

如果cur是重复项的话 prev就指向cur的next

之后prev走到cur的位置 cur往前跑 不断循环 之后返回head就可以了

代码表示如下

struct ListNode* deleteNode(struct ListNode* head, int val)
{
    // 首先判断 如果整个链表为空 直接返回一个空就好
    if(head==NULL)
    {
        return NULL;
    }

    // 之后我们使用两个指针来进行删除 一个当前指针 一个next指针 
    struct ListNode* cur = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* prev = (struct ListNode*)malloc(sizeof(struct ListNode));

    cur = head;
    // 前面以及判断过head不为空 这里放心用
    while(cur && cur ->val == val)
    {
        prev = cur;
        cur=cur->next;
        free(prev);
        head = cur;
    }
    



    // 后面开始考虑普通情况

    while(cur)
    {
        // 开始找要删的数据 找不到就往前遍历
        if(cur->val==val)
        {
            prev ->next = cur->next;
            prev = cur;
            cur = cur->next;
            free(prev);
        }
        else
        {
            prev = cur;
            cur = cur->next;
        }

    }

    return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

队列和栈

还是跟前面一样 在看后面的内容之前需要有队列相关知识

具体大家可以看看我写的这两篇文章啊

初阶数据结构 队列

初阶数据结构 栈

1. 循环队列

这道题前面的博客已经写过了 这里简单介绍下思路

首先我们可以设置两个指针 分别指向头尾

但是我们这里发现 不太好判断队列的空 满是吧

那么这里我们可以增加一个参数 size

如果size= 0

是不是就代表队列为空

如果size = 最大值

是不是就代表队列为满

对这道题有兴趣的同学可以看看我的这篇博客 试着用我这里提供的方法将这个循环队列写出来

循环队列

2. 特殊栈

要求我们实现一个特殊的栈

它有两个功能

一个功能和基础的栈一样

还有一个功能是能够返回这个栈里面的最小值

这个思路也很简单

我们用两个栈来实现就好了

一个栈实现全部的普通功能

一个栈压栈的时候

1 如果为空 就压栈第一个元素

2 如果不为空 压栈当前元素和栈内最小元素两者的较小值

这样子就可以啦

3. 队列与栈

用两个队列实现栈

用两个栈实现队列

这两个题目前面的博客中均有涉及

大家可以移步观看

队列实现栈

栈实现队列

总结

简单介绍了几种基本数据结构的面试题目
由于博主水平优先所以出现错在所难免 希望大佬看到可以指正
如果帮助到大家别忘了一键三连啊
阿尼亚 哇酷哇酷！