今天分享的内容是LeetCode #25 K个一组反转链表这个题目，详细内容如下：
初始化：3个指针 1）pre指针指向已经反转好的链表的最后一个节点，最开始没有反转，所以指向nullptr 2）current指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向head 3）nextnode指针指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存 接下来，循环执行以下三个操作 1）nextnode = current->next, 保存作用 2）current->next = pre 未反转链表的第一个节点的下个指针指向已反转链表的最后一个节点 3）pre = current， current = nextnode; 指针后移，操作下一个未反转链表的第一个节点 循环条件，当然是current != nullptr 循环结束后，current当然为nullptr，所以返回pre，即为反转后的头结点
本期例题：LeetCode 206 - Reverse Linked List[1]（Easy）
前言 本系列主要讲解链表的经典题 注：划重点！！必考~ 反转链表 力扣链接：206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com) 题目描述： 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表 示例： 📷 提示： 链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000 解题思路： 这里我们采用三指针进行反转链表： 指针cur进行遍历链表 指针next记录cur的下一个指针，防止反转时下一个节点地址丢
最近在 LeetCode 上刷题，对于 链表 类型的题目刷的比较多，所以打算写一篇文章，分享一下练习链表类型题目的思考和心得
https://leetcode-cn.com/problems/reverse-linked-list/
给定一个指向链表头节点的指针，任务是反转链表。我们需要通过更改节点之间的链接来反转列表。
您在循环中为每个节点重新分配内存，这实际上是在创建原始链表的深拷贝的反转版本，而不是就地反转链表。如果只需要反转链表而不创建其副本，则无需分配新的节点内存。
通常来说，链表的问题从概念上讲很简单，更多时单纯的考察编码能力，而不是设计和解决算法。
在链表：听说用虚拟头节点会方便很多？中，我们讲解了链表操作中一个非常总要的技巧：虚拟头节点。
链表反转在面试中非常常见，我也在面试中遇到过这道题。在本篇文章中我们先说说如何用迭代法求解该题。
如果你和小鹿一样，刚开始对链表的操作代码实现很懵的话，不妨按照小鹿经过一个月的时间对链表相关操作以及题型的整理总结，由浅入深进行适当的练习，我相信，当你真正的练习完这些题目，不但会让你放下对链表心理上的困惑，而且对你学习其他数据结构有很大的信心和帮助！
链表反转是⼀个出现频率特别⾼的算法题，笔者过去这些年⾯试，⾄少遇到过七⼋次。其中更夸张的是曾经两天写 了三次，上午YY，下午⾦⼭云，第⼆天快⼿。链表反转在各⼤⾼频题排名⽹站也⻓期占领前三。⽐如⽜客⽹上这个 No 1 好像已经很久了。所以链表反转是我们学习链表最重要的问题，没有之⼀。 那为什么反转这么重要呢？因为反转链表涉及结点的增加、删除等多种操作，能⾮常有效考察对指针的驾驭能⼒和 思维能⼒。 另外很多题⽬也都要⽤它来做基础， 例如指定区间反转、链表K个⼀组翻转。还有⼀些在内部的某个过程⽤到了反 转，例如两个链表⽣成相加链表。还有⼀种是链表排序的，也是需要移动元素之间的指针，难度与此差不多。接下 来我们就具体看⼀下每个题⽬。
之前的文章「递归反转链表的一部分」讲了如何递归地反转一部分链表，有读者就问如何迭代地反转链表，这篇文章解决的问题也需要反转链表的函数，我们不妨就用迭代方式来解决。
在链表：听说用虚拟头节点会方便很多？中，我们讲解了链表操作中一个非常重要的技巧：虚拟头节点。
k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
LeetCode 是著名的练习数据结构与算法的网站，很多学习程序设计的人都在刷上面的题来巩固和提高自己的数据结构以及算法的能力。同时，该网站的很多数据结构及算法题都是面试中的真题。
Given a singly linked list, determine if it is a palindrome.
NC21 链表内指定区间反转 https://www.nowcoder.com/ta/job-code-high-week?tag=580) 描述 将一个节点数为 size 链表 m 位置到 n 位置
题目描述：定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。 例如： 给出的链表为 1→ 2→ 3 → 4→ 5 → NULL, m=2,n=4m=2,n=4, 返回 1→ 4→ 3 → 2 → 5 → NULL。
今天聊聊如何判断一个链表是不是回文链表。之前有两篇文章写了回文串和回文序列相关的问题：
反转链表是程序员必备的基本素养，经常在面试、笔试的过程中出现。一直觉得反转链表实现代码不是很好理解，决定搬leetcode那道经典反转链表题出来，用十多张图去解析它，希望加深大家对链表反转的理解，谢谢阅读。
因为回文串长度可能为奇数也可能是偶数，长度为奇数时只存在一个中心点，而长度为偶数时存在两个中心点，所以上面这个函数需要传入l和r。
链表的操作是数据结构中最基础的算法之一，反转列表也是一道经典的笔试题。很多公司的面试题库中都有这道题，有的公司明确题目要求不能使用额外的节点存储空间，有的没有明确说明，但是如果面试者使用了额外的节点存储空间做中转，会得到一个比较低的分数。本题选自leetcode的206题，感兴趣的小伙伴可以去练习一下。206.反转链表
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
解题思路： 题目很简单。 既然给出的链表已经排好序，我们只需要对比当前节点的元素大小，较小的元素节点优先放入新链表中，重复操作，最后返回新链表即可：
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。
今天给大家带来的专题是《链表》。很多人觉得链表是一个很难的专题。实际上，只要你掌握了诀窍，它并没那么难。接下来，我们展开说说。
在上一篇《图解精选 TOP 面试题 005 | 反转链表之迭代求解》中，我们介绍了该题的迭代求解法，本篇再说说如何进行递归求解。
简单的方法是遍历一边链表，存入数组，再从首尾往中间判断是否相等。但是题目说了，进阶的解法是空间复杂度为O(1)，首先排除递归反转链表，倒是可以利用迭代来反转链表。在优化下，不用反转整条链表来比较，只需反转半条即可。
输入：[1,2,3,4,5] 输出：此列表中的节点 3思路分析:要找到链表的中间节点，可以定义两个指针，一个是慢指针slow，另一个是快指针fast。初始，慢指针slow和快指针fast都指向链表的头节点。然后，快指针fast每次向前移动两步，慢指针slow每次向前移动一步，当快指针fast不能继续向前移动时，慢指针slow所指的节点就是中间节点。对于节点个数为奇数的链表来说，其中间节点只有一个；而对于节点个数为偶数的链表来说，其中间节点有两个。接着，我们就通过动画来看下如何通过快慢指针找到链表的中间节点。1.当快指针fast向前移动的条件是：fast.next!=null && fast.next.next != null时：对于节点个数为奇数的链表来说，动画演示如下，此时链表的中间节点是节点3。对于节点个数为偶数的链表来说，动画演示如下，此时链表的中间节点是节点2，即在2和3这两个中间节点中，找到是第一个中间节点。2.当快指针fast向前移动的条件是：fast!=null && fast.next != null时：对于节点个数为奇数的链表来说，动画演示如下，此时链表的中间节点是节点3。对于节点个数为偶数的链表来说，动画演示如下，此时链表的中间节点是节点3，即在2和3这两个中间节点中，找到是第二个中间节点。 题目要求的是如果有两个中间节点，则返回第二个中间节点。因此，对于该题目而言，快指针fast向前移动的条件是：fast!=null && fast.next != null。代码实现： 02LeetCode #206反转链表题目描述：反转一个单链表。示例:输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL思路分析:对于题目给出的链表，简化如下：由于只知道链表的头节点head，因此需要从头节点head开始反转。头节点head在反转之后，就成为了链表的尾节点，而尾节点的后继指针是指向null的。因此，需要定义一个空节点，在这里我们用prev表示。同时，对于当前考察的节点，我们用cur表示。接着要做的就是，将cur所指节点的后继指针指向prev指向的节点。但是，这么做之后，cur所指节点的原本的后继节点就从链表中丢失了。因此，在将cur所指节点的后继指针指向prev指向的节点前，需要先用变量nextNode指向cur所指节点的原本的后继节点。 在完成cur所指节点的反转之后，就要继续反转下一个节点了。因此，先prev指向cur所指向的节点，作为下一个待反转节点反转之后的后继节点。然后，cur指向nextNode指向的节点，表示其是下一个待反转的节点。动画演示：代码实现： 03LeetCode #143重排链表题目描述：给定一个单链表 L：L0→L1→…→Ln-1→Ln ， 将其重新排列后变为：L0→Ln→L1→Ln-1→L2→Ln-2→…你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。示例1:给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.示例2：给定链表 1->2->3->4, 重新排列为 1->4->2->3.思路分析:通过观察给到的示例，其结果是将原链表的前半部分和原链表的后半部分反转之后的链表进行合并得到的。因此，整体思路就是：首先，找到链表的中间节点，方法如上述的#86题；接着，将链表的后半部分反转，放入如上述的#206题；然后，将链表的前半部分和链表的后半部分反转后的结果进行合并。 示例1给出的链表结构如下：中间节点是节点3，链表的前半部分和后半部分如下：链表合并的动画演示如下：整个题目的完整代码实现如下：
package Leetcode真题分门别类.链表; /** * @Author bennyrhys * @Date 2020-05-29 15:39 * 思想： * 链表翻转，直接改变指针指向 反转n-m次 * head表示需要反转的头节点，pre表示需要反转头节点的前驱节点 * 保存状态需要创建三个指针（pre前 cur当前 next下一个） * 将head的next节点移动到需要反转链表部分的首部 * 第一次反转：1(head) 2(next) 3 4 5 反转为 2 1 3 4 5
示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL
假设链表为 1 → 2 → 3 → ∅，我们想要把它改成 ∅ ← 1 ← 2 ← 3。
假设存在链表 1->2->3->4->5->NULL，我们想要把它改成 5->4->3->2->1->NULL。在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！
输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5] 示例 2：
若要满足 O(1) 空间复杂度，则不能借助于列表或栈结构存储数据。因为单链表不像字符串可以进行直接访问，所以这里采用的方式为，找到单链表中间元素，并反转单链表前半部分，然后与单链表后半部分进行比较是否为回文结构。
完整高频题库仓库地址：https://github.com/hzfe/awesome-interview
承接第3篇文章《开启算法之路，还原题目，用debug调试搞懂每一道题》，本篇文章继续分享关于链表的算法题目。
题目描述 输入一个链表，反转链表后，输出链表的所有元素。 思路 思路一： 迭代：将当前节点和下一节点保存起来，然后将当前节点反转。 思路二： 递归：利用递归走到链表的末端，然后再更新每一个节点的next值 ，实现链表的反转。 代码实现 package LinkedList; /** * 反转链表 * 输入一个链表，反转链表后，输出链表的所有元素。 */ public class Solution35 { /** * 递归 * * @param head
示例 1： 输入：head = [1, 2, 3, 4, 5] 输出：[5, 4, 3, 2, 1]
上篇文章 递归反转链表：如何拆解复杂问题 讲了如何递归地反转一部分链表，有读者就问如何迭代地反转链表，这篇文章解决的问题也需要反转链表的函数，我们不妨就用迭代方式来解决。
题目链接——206. 反转链表 - 力扣（LeetCode） (leetcode-cn.com)
领取专属 10元无门槛券
手把手带您无忧上云
