第一题：反转链表
原题：反转链表
1.题目描述
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围： 0≤n≤1000
要求：空间复杂度 O(1) ，时间复杂度 O(n)。
如当输入链表{1,2,3}时，经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
2.示例
示例1
输入： {1,2,3}
返回值： {3,2,1}
示例2
输入： {}
返回值： {}
说明：空链表则输出空
3.个人思路分析
双链表求解是把原链表的结点一个个摘掉，每次摘掉的链表都让他成为新的链表的头结点，然后更新新链表。下面以链表1→2→3→4为例画个图来看下：
继续往下看：
他每次访问的原链表节点都会成为新链表的头结点，最后再来看下代码：
4.题解
Java版本代码实现：
public ListNode ReverseList(ListNode head) { //新链表 ListNode newHead = null; while (head != null) { //先保存访问的节点的下一个节点，保存起来 //留着下一步访问的 ListNode temp = head.next; //每次访问的原链表节点都会成为新链表的头结点， //其实就是把新链表挂到访问的原链表节点的 //后面就行了 head.next = newHead; //更新新链表 newHead = head; //重新赋值，继续访问 head = temp; } //返回新链表 return newHead; }
第二题：链表内指定区间反转
原题：链表内指定区间反转
1.题目描述
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 O(1)。
例如：
给出的链表为 1→2→3→4→5→NULL, m=2,n=4m=2,n=4,
返回 1→4→3→2→5→NULL.
数据范围： 链表长度 0<size≤1000，0 < m ≤n ≤ size，链表中每个节点的值满足 ∣val∣≤1000 。
要求：时间复杂度 O(n)，空间复杂度 O(n)
进阶：时间复杂度 O(n)，空间复杂度 O(1)
2.示例
示例1
输入： {1,2,3,4,5},2,4
返回值： {1,4,3,2,5}
示例2
输入： {5},1,1
返回值： {5}
3.个人思路分析
在学会了反转链表之后，要解决这个问题就很简单了，前一题是整个链表反转，这一题是部分反转，这上一题就是这道题的前置问题啊。那我们肯定是要先找到了第m个位置才能开始反转链表，而反转的部分就是从第m个位置到第n个位置，反转这部分的时候就参照上面第一题的反转链表：
4.题解
Java版本代码实现：
import java.util.*; public class Solution { public ListNode reverseBetween (ListNode head, int m, int n) { //加个表头 ListNode res = new ListNode(-1); res.next = head; //前序节点 ListNode pre = res; //当前节点 ListNode cur = head; //找到m for(int i = 1; i < m; i++){ pre = cur; cur = cur.next; } //从m反转到n for(int i = m; i < n; i++){ ListNode temp = cur.next; cur.next = temp.next; temp.next = pre.next; pre.next = temp; } //返回去掉表头 return res.next; } }
第三题：链表中的节点每k个一组翻转
1.题目描述
将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表：
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。
数据范围：0 0≤n≤2000 ，1 ≤k≤ 2000 ，链表中每个元素都满足 0≤val≤1000
要求空间复杂度 O(1)，时间复杂度 O(n) 。
例如：
给定的链表是 1→2→3→4→5
对于 k = 2 , 你应该返回 2→1→4→3→5
对于 k = 3 , 你应该返回 3→2→1→4→5
2.示例
示例1
输入： {1,2,3,4,5},2
返回值： {2,1,4,3,5}
示例2
输入： {},1
返回值： {}
3.个人思路分析
关于这道经典的算法题目，我的思路大概分一下几个步骤：
找到待翻转的k个节点（注意：若剩余数量小于 k 的话，则不需要反转，因此直接返回待翻转部分的头结点即可）。
对其进行翻转。并返回翻转后的头结点（注意：翻转为左闭又开区间，所以本作的尾结点其实就是下一作的头结点）。
对下一轮 k 个节点也进行翻转操作。
将上一轮翻转后的尾结点指向下一轮翻转后的头节点，即将每一轮翻转的k的节点连接起来。
图解：
4.题解
Java版本代码实现：
public class Solution { /** * * @param head ListNode类 * @param k int整型 * @return ListNode类 */ public ListNode reverseKGroup (ListNode head, int k) { // write code here ListNode cur = head; int count = 0; // 找到待反转的第k个结点 while (cur != null && count != k) { cur = cur.next; count++; } if (count == k) { // 递归 cur = reverseKGroup(cur, k); // 反转列表 while (count != 0) { count--; ListNode tmp = head.next; head.next = cur; cur = head; head = tmp; } // 拼接后续的链表 head = cur; } return head; } }
