面试官: “反转链表”有哪些实现方式？

清疚 2022-10-16 15:29 266阅读 0赞

hello大家好，我是小慕呀，愉快的周末结束啦，明天得去上班咯！![b4592971cff3b66c7843d3752e3561dd.png][] 最近老是在微博热搜中看到“躺平”一词，出现的次数太多太多了，多的都数不清了，我们一起看下图 ![b8be374f89240244ea245043141e1f1a.png][]![b8be374f89240244ea245043141e1f1a.png][]

![e06b5743fc38517778c71c910f3d3a35.png][]

然后看微博评论的时候看到很多好笑的，特别好笑，我随便列出几个好笑的

> 你们都躺平，我赚谁的培训费？
> 
>  
> 
> 只要我躺平，镰刀就割不到我！
> 
>  
> 
> 我现在听什么马云俞敏洪之类讲话我就烦躁想抽他们！
> 
>  
> 
> 你们随意，我先躺为敬
> 
>  
> 
> 资本家还是别发声了，他屁股都是歪的

**我觉得吧，大家讨厌的不是资本家也不是有钱人，本质上是讨厌自己怎么没有成为这类人。俗话说“屁股决定脑袋”嘛，说的大概也是这个意思，所处位置不同，想法不同，可以理解的，哈哈！！！**

好啦，和大家唠嗑了一会儿了，废话不多说了，那今天晚上我们加个餐，学习一下“反转链表”呗！

所谓反转链表，就是将链表整体“反过来”，将头变成尾、尾变成头，如下图所示

![00d7e9a92c31aa2795386019da1b2527.png][]

**一、利用“栈”的特性来实现**

我们都知道栈是“先进后出”的，刚好适用于将线性表的顺序颠倒这类问题

public ListNode reverseList(ListNode head) {
            Stack<ListNode> stack = new Stack<>();     //把链表节点全部摘掉放到栈中     while (head != null) {
                stack.push(head);         head = head.next;     }     if (stack.isEmpty())         return null;    ListNode node = stack.pop();  //弹出栈顶的元素做新链表的头结点    ListNode dummy = node;    //栈中的结点全部出栈，然后重新连成一个新的链表    while (!stack.isEmpty()) {
               ListNode tempNode = stack.pop();        node.next = tempNode;        node = node.next;    }    //最后一个结点就是反转前的头结点，一定要让他的next    //等于空，否则会构成环    node.next = null; //这个时候node已经变成新链表的最后一个节点了    return dummy;}

**二、利用“头插法”来实现**

**  **不熟悉头插法的朋友们，看下图即可明白啥是“头插法”

![2ee047b0c7ca8e33176864e7a5654a4d.png][]

**实现代码如下**

struct ListNode *reverseList(struct ListNode* head) {
         struct ListNode *newHead = NULL;  struct ListNode *node;  while (head != NULL) {
           //1. 对之前的链表做头删    node = head;    head = head->next;    //2. 对新链表做头插    node->next = newHead;    newHead = node;  }  return newHead;}

**三、利用“三指针”来实现**

首先让P1指针指向链表的头结点，让P2指向链表的第二个节点，让P0指向链表的尾部

![fa0f66e2534b8c83c09058f40f7d3e69.png][]

然后将P1和P2之间的那个指针给干掉，然后再让P1所指的那个节点的next箭头指向P0，如下图，(*让P1节点和P0节点之间加一个箭头，就相当于让头结点指向了尾结点，这样不就有点反转的意思了吗？**![1cd2493f34a221e38b90967883eafb0c.png][]*)

然后把P2，P1指针往后移一步,分别指向下一个节点，然后让P0指向链表的头部，再然后就是在P0和P1之间加一个红色箭头，如下图所示

![dcf0b26730d0431f8798e63a4f9c5e3d.png][]

然后一直把P2,P1,P0指针依次往后挪动，一边挪，一边加红色箭头，如下图所示，看红色的箭头，这样不就达到了链表反转的效果了吗？

![b08aff49ddb81bdbdf39ee5685fd79a4.png][]

代码如下：

struct ListNode *reverseList(struct ListNode* head) {
         if (head == NULL) {
           return NULL;  }  struct ListNode *p0 = NULL;  struct ListNode *p1 = head;  struct ListNode *p2 = head->next;  while (p1 != NULL) {
           p1->next = p0;    p0 = p1;    p1 = p2;    if (p2 != NULL) {
             p2 = p2->next;    }  }  return p0;}

**四、利用“递归法”来实现**

递归说白了就是“套娃”，所以想要学好递归，首先把套娃玩具玩它个几百遍，哈哈![79bf89192698ae60afe7cc56711c1243.png][]![79bf89192698ae60afe7cc56711c1243.png][]![79bf89192698ae60afe7cc56711c1243.png][]， 下图就是递归的思想。

**下面的实现代码也是按上图的思想来实现的**

1  public ListNode reverseList(ListNode head) {
        2    //终止条件 3    if (head == null || head.next == null) 4        return head; 5    //保存当前节点的下一个结点 6    ListNode next = head.next; 7    //从当前节点的下一个结点开始递归调用 8    ListNode reverse = reverseList(next); 9    //reverse是反转之后的链表，因为函数reverseList表示的是对链表的反转，所以反转完之后next肯定11    // 是链表reverse的尾结点，然后我们再把当前节点head挂到next节点的后面就完成了链表的反转。13    next.next = head;14    //这里head相当于变成了尾结点，尾结点都是为空的，15    //否则会构成环16    head.next = null;17    return reverse;18}

好啦，今天的内容到这里就结束了，行百里者半九十，请不要半途而废，好吗？![54fae291b09d072c821393b6acb4c1b1.png][]![54fae291b09d072c821393b6acb4c1b1.png][]![54fae291b09d072c821393b6acb4c1b1.png][]

**历史推文**

[“快慢指针法“”的一些骚操作][Link 1]

[都2021年了，你还不懂幂等性问题的解决方案？][2021]

** **[为啥Spring事务失效了,你踩坑了吗？][Spring]

[    今天你又被内卷了吗？“躺平”好不好？][Link 2]

[Eureka和Zookeeper到底有什么区别 ？][Eureka_Zookeeper_]

[听说你还不懂什么是CAP理论？][CAP]

[TCP三次握手、四次挥手很难？NO][TCP_NO]

[位运算的奇“赢”技巧][Link 3]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjQxOTU3_size_16_color_FFFFFF_t_70][]

[b4592971cff3b66c7843d3752e3561dd.png]: https://img-blog.csdnimg.cn/img_convert/b4592971cff3b66c7843d3752e3561dd.png
[b8be374f89240244ea245043141e1f1a.png]: /images/20221014/792791f57de1422a95b7708f6f2531b0.png
[e06b5743fc38517778c71c910f3d3a35.png]: /images/20221014/a3ab0372580c44789ebf838819a161a3.png
[00d7e9a92c31aa2795386019da1b2527.png]: /images/20221014/82095f83e71f409799000910b3df6e88.png
[2ee047b0c7ca8e33176864e7a5654a4d.png]: /images/20221014/0ea58407f14b40bebbecb8446e305c89.png
[fa0f66e2534b8c83c09058f40f7d3e69.png]: /images/20221014/e56631350b984f54bfcdbe9c7f9e26f4.png
[1cd2493f34a221e38b90967883eafb0c.png]: /images/20221014/b3105aeeefea49c5b23ad95f5b3dd3a4.png
[dcf0b26730d0431f8798e63a4f9c5e3d.png]: /images/20221014/3324c33f32ed4030b8c25fc23b94e85e.png
[b08aff49ddb81bdbdf39ee5685fd79a4.png]: /images/20221014/7dde3dbbb08449708fbf053eb3677221.png
[79bf89192698ae60afe7cc56711c1243.png]: /images/20221014/7a53ea0b06ce4d2d949da52802f78b1c.png
[54fae291b09d072c821393b6acb4c1b1.png]: /images/20221014/095ef632e8df4f6791b802c39312282f.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzkwOTI0NjkyMA==&mid=2247483992&idx=1&sn=28a529af488083835991ab9397393f3e&chksm=c13ceafff64b63e9345107e5acc55acf228c34dbfbcc7feb318d4a17de43908a016e11e50055&scene=21#wechat_redirect
[2021]: http://mp.weixin.qq.com/s?__biz=MzkwOTI0NjkyMA==&mid=2247483903&idx=1&sn=ba689887983608563237a6c04fe6213d&chksm=c13ce958f64b604e82d058d19d49e7865b5e6e920fb1127dc824b2b178dc5cefd988d56c24ac&scene=21#wechat_redirect
[Spring]: http://mp.weixin.qq.com/s?__biz=MzkwOTI0NjkyMA==&mid=2247483844&idx=1&sn=20df94a9950fc630dda4c4e8c3b7dcb2&chksm=c13ce963f64b60759104af03420b815109694469002adc07abd11aba6a50146e48045e1c0d9b&scene=21#wechat_redirect
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzkwOTI0NjkyMA==&mid=2247483814&idx=1&sn=43ba2ed605ec1db569ad9212d781fd9d&chksm=c13ce901f64b601737fcdca7844929c2f900a4065d941c31925f455dff324003f98c004e77b8&scene=21#wechat_redirect
[Eureka_Zookeeper_]: http://mp.weixin.qq.com/s?__biz=MzkwOTI0NjkyMA==&mid=2247483795&idx=1&sn=a386540c04130ed1bef05dbd57bfd27a&chksm=c13ce934f64b60222d0307e04ae2b6ef3b9d78b315f2abf72afc8c30fcc2e270cc65283467d0&scene=21#wechat_redirect
[CAP]: http://mp.weixin.qq.com/s?__biz=MzkwOTI0NjkyMA==&mid=2247483766&idx=1&sn=4aeb71616335d0a1aa6dc76bdb2581d5&chksm=c13ce9d1f64b60c78fa49c8cb5c35cb93fc036616a46cfba94a0868e48d68992084361db7f47&scene=21#wechat_redirect
[TCP_NO]: http://mp.weixin.qq.com/s?__biz=MzkwOTI0NjkyMA==&mid=2247483739&idx=1&sn=383992db5b1fe3b010d5f56ce331705c&chksm=c13ce9fcf64b60ea4c8d188baa5cdbe35f78f56881e47793efa3dfc79fa437c6ced0a7b2bd89&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzkwOTI0NjkyMA==&mid=2247483708&idx=1&sn=ab599e969c587ec1e5ef48d91e4f339b&chksm=c13ce99bf64b608d268c762f908415bfd8c8c5ea73f20a20746b2de179e5575fe82ab5918826&scene=21#wechat_redirect
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwMjQxOTU3_size_16_color_FFFFFF_t_70]: /images/20221014/e518c78c2d1c4ee18fd40ec3e780ca0d.png