【数据结构与算法】四链表反转

古城微笑少年丶 2022-08-20 09:26 208阅读 0赞

# **【数据结构与算法】四 链表 反转** #

# **链表** #

前面我们提到数组,今天我们来聊一聊链表,链表也是一基础数据结构,在很多语言原生纯在.好了,我们不废话直接自己来实现个链表练练手…

C++

#include <iostream>
    
    struct node{
        int num;
        node* next;
    };
    
    void out(node* head){
        node* iterator = head ;
        while(iterator){
            std::cout << iterator->num << std::endl;
            iterator = iterator->next;
        }
    
    }
    
    int main(int argc, const char * argv[]) {
        node* head = nullptr;
        node* newNode = nullptr;
        for(int i = 0; i < 5; i++){
            newNode = new node;
            newNode->num = i;
            newNode->next = head;
            head = newNode;
        }
        out(head);
    }

struct结构体定义了一个node , node中包含整数型 num 与node型 next .  
我们在main的for循环中新建立了5个node , 并把新建立的Node 的next指向上一个node , 这样就形成了一个链表 . 具体机构看下图 …

![这里写图片描述][20160223200446242]

这五个元素可以是在内存的任何地方，  
解决了数组插入，与删除的问题，比如现在4与3之间插入3.5 ，只需要让4的next指向3.5，并让3.5的next指向3这个Node就可以了 ，删除也是同样的道理。所以就数组与链表来说链表在插入与删除的性能要高于数组，但是链表随机访问性能要低于数组，链表取第一个元素与第100个元素的时间是相差很大的，随着链表的增大，访问尾部的元素时间也就越长。

--------------------

# **反转** #

数组是我们做了数组的反转，并对数组反转做了简单的时间复杂度计算（具体看我前面的博客），接下来我们实现链表的反转。其实只要将链表中各个元素的指针反转就可以了，把问题分解开就是让4->next = nullptr ; 3->next = 4 ; 以此类推，看来这是一个重复的工作，那我们就用递归来实现它。

node* reverse(node* first){
        if(first->next == nullptr)
            return first;
        node* second = first->next;
        node* new_head = reverse(second);
        second->next = first;
        first->next = nullptr;
        return new_head;
    }

我们来简单的分析一下这个方法， 在方法中我们实现了第一个元素与第二个元素next的反转，那么接下来就时第二个元素与第二个元素的反转，以此类推，方法的最后我们把反转后的新的链表头返回 。

![这里写图片描述][20160223225251851]

--------------------

# **基础数据结构** #

我们前面提到的数组与链表事基础数据结构，那么为什么说着两者是基础的数据结构呢？  
栈stack 这种数据结构就是只可以从头取数据。  
队列 一头进，一头出 。  
哈希表 …  
这些我们在后面都会有介绍 。

--------------------

# **最后** #

通过上面一些简单的讲解，  
相信朋友们已经知道其原理及特性了。  
本人能力有限,  
如发现错误或不合理欢迎指正…

--------------------

[20160223200446242]: /images/20220731/7619c8f37f9145d79bfc64dcea14d648.png
[20160223225251851]: /images/20220731/95d2029ec10342aea70a0541351dd8d7.png