class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1">

 但是通过上面的代码分析，while中定义的bar是否多余？是否可以更近一步？

通过图可以知道，head结点在第一次更改后 -> next 就指向null了，其实这个是可以利用起来的，用来指向node后的结点，在最后再更新成null，省下一个结点的定义。

过程如图：

 代码如下：

 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1"> class="hljs-ln-code"> class="hljs-ln-line">/**
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="2"> class="hljs-ln-code"> class="hljs-ln-line"> * Definition for singly-linked list.
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="3"> class="hljs-ln-code"> class="hljs-ln-line"> * struct ListNode {
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="4"> class="hljs-ln-code"> class="hljs-ln-line"> *     int val;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="5"> class="hljs-ln-code"> class="hljs-ln-line"> *     ListNode *next;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="6"> class="hljs-ln-code"> class="hljs-ln-line"> *     ListNode() : val(0), next(nullptr) {}
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="7"> class="hljs-ln-code"> class="hljs-ln-line"> *     ListNode(int x) : val(x), next(nullptr) {}
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="8"> class="hljs-ln-code"> class="hljs-ln-line"> *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="9"> class="hljs-ln-code"> class="hljs-ln-line"> * };
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="10"> class="hljs-ln-code"> class="hljs-ln-line"> */
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="11"> class="hljs-ln-code"> class="hljs-ln-line">class Solution {
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="12"> class="hljs-ln-code"> class="hljs-ln-line">public:
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="13"> class="hljs-ln-code"> class="hljs-ln-line">    ListNode* reverseList(ListNode* head) {
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="14"> class="hljs-ln-code"> class="hljs-ln-line">        if(head == nullptr) return head;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="15"> class="hljs-ln-code"> class="hljs-ln-line">        ListNode* pre = head;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="16"> class="hljs-ln-code"> class="hljs-ln-line">        ListNode* node = head -> next;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="17"> class="hljs-ln-code"> class="hljs-ln-line">        while(node != nullptr){
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="18"> class="hljs-ln-code"> class="hljs-ln-line">            head -> next = node -> next;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="19"> class="hljs-ln-code"> class="hljs-ln-line">            node -> next = pre;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="20"> class="hljs-ln-code"> class="hljs-ln-line">            pre = node;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="21"> class="hljs-ln-code"> class="hljs-ln-line">            node = head -> next;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="22"> class="hljs-ln-code"> class="hljs-ln-line">        }
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="23"> class="hljs-ln-code"> class="hljs-ln-line">        return pre;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="24"> class="hljs-ln-code"> class="hljs-ln-line">    }
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="25"> class="hljs-ln-code"> class="hljs-ln-line">}; class="hide-preCode-box"> class="hljs-button signin" data-title="登录后复制" data-report-click="{"spm":"1001.2101.3001.4334"}" onclick="hljs.signin(event)">

 解法二： 递归

时间复杂度O(N)，空间复杂度O(N)主要取决于递归调用的栈空间，最多为 N 层。

递归的方法不太好理解，但是这道题用递归是完美的利用了递归的特性，非常妙。

• 使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 ret .
• 此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
• 同时让当前结点的 next 指针指向 NULL ，从而实现从链表尾部开始的局部反转
• 当递归函数全部出栈后，链表反转完成。

代码如下： 

 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="1"> class="hljs-ln-code"> class="hljs-ln-line">class Solution {
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="2"> class="hljs-ln-code"> class="hljs-ln-line">public:
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="3"> class="hljs-ln-code"> class="hljs-ln-line">    ListNode* reverseList(ListNode* head) {
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="4"> class="hljs-ln-code"> class="hljs-ln-line">        if (head == NULL || head->next == NULL) {
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="5"> class="hljs-ln-code"> class="hljs-ln-line">            return head;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="6"> class="hljs-ln-code"> class="hljs-ln-line">        }
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="7"> class="hljs-ln-code"> class="hljs-ln-line">        ListNode* ret = reverseList(head->next);
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="8"> class="hljs-ln-code"> class="hljs-ln-line">        head->next->next = head;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="9"> class="hljs-ln-code"> class="hljs-ln-line">        head->next = NULL;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="10"> class="hljs-ln-code"> class="hljs-ln-line">        return ret;
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="11"> class="hljs-ln-code"> class="hljs-ln-line">    }
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="12"> class="hljs-ln-code"> class="hljs-ln-line">};
 class="hljs-ln-numbers"> class="hljs-ln-line hljs-ln-n" data-line-number="13"> class="hljs-ln-code"> class="hljs-ln-line">  class="hljs-button signin" data-title="登录后复制" data-report-click="{"spm":"1001.2101.3001.4334"}" onclick="hljs.signin(event)">

解法三： 辅助存储（取巧做法）

时间复杂度O(N)，空间复杂度O(N)

这种做法就是偏向于一种取巧做法，和链表的特性无关，这里不再赘述。

主要过程：

• 先定义一个容器用来存储链表数值。（栈或者数组）；
• 之后先遍历一遍，获取数值，存进去。
• 之后再遍历一遍，将之前获取的数值重新赋值到原链表。（栈就顺序出栈，数组就倒序输出）

 上一篇： 从B站 (哔哩哔哩) 泄露的源码里发现了B站视频推荐的秘密

下一篇： 400+条实用C/C++框架、库、工具整理 ，你能想到的都在这里了

如果有什么要补充的，欢迎下方👇评论区留言~

1份赞许 = 100分的认可，如果感觉还不错，点个赞👍 支持一下吧 ~

不定期分享 有趣、有料、有营养内容，欢迎 订阅关注 🤝 我的博客 ，期待在这与你相遇 ~

发表评论

登录后才能发表评论和回复 注册

/ 登录

提交评论

评论记录：

未查询到任何数据！

回复评论：

×

关闭 提交评论