History is apt to judge harshly those who sacrifice tomorrow for today.
历史往往对那些为了今天而牺牲明天的人作出严厉的判决。
问题描述
来源：LeetCode第92题
难度：中等
给你单链表的头指针head和两个整数left和right，其中left<=right。请你反转从位置left到位置right的链表节点，返回反转后的链表 。
示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
提示：
-
链表中节点数目为 n
-
1 <= n <= 500
-
-500 <= Node.val <= 500
-
1 <= left <= right <= n
头插法解决
之前讲过链表的全部反转《432，剑指 Offer-反转链表的3种方式》，而这题只要求反转链表的部分节点，如果直接使用多个指针对需要反转的节点前后两两交换，也是可以解决的。
但这里我们使用一种更加容易理解的方式来解决，就是使用头插法，举个例子，比如我们要反转[1,2,3,4]
-
第一步2插入到前面[2,1,3,4]
-
第二步3插入到前面[3,2,1,4]
-
第三步4插入到前面[4,3,2,1]
只需要把后面不停的往前面插入即可完成反转，这里以示例一为例画个图来看下
再来看下代码
1public ListNode reverseBetween(ListNode head, int m, int n) {
2 //为了方便处理，先创建一个哑节点，让他指向head
3 ListNode dummy = new ListNode(0);
4 dummy.next = head;
5
6 //记录开始反转节点的前一个节点
7 ListNode pre = dummy;
8 for (int i = 0; i < m - 1; i++) {
9 pre = pre.next;
10 }
11 //记录开始反转的节点，我们把它后面需要反转的的节点
12 //都移动到前面
13 ListNode cur = pre.next;
14
15 //采用头插法，把后面的节点都插入到前面
16 for (int i = 0; i < n - m; i++) {
17 ListNode next = cur.next;
18 cur.next = next.next;
19 next.next = pre.next;
20 pre.next = next;
21 }
22 return dummy.next;
23}
总结
链表的节点交换一般没什么难度，但如果不仔细很容易出错，对于链表的交换最好在纸上一步步把它画出来，这样才更容易理解。
截止到目前我已经写了500多道算法题了，为了方便大家阅读，我把部分算法题整理成了pdf文档，目前有1000多页，大家可以在公众号中回复关键字“pdf”即可获取下载链接。