Leetcode 分类刷题 —— 链表类（Linked List）
1、题目
Leetcode 92. Reverse Linked List II
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
2、思路
思路：head表示需要反转的头节点，pre表示需要反转头节点的前驱节点
我们不断地将head的next节点移动到需要反转链表部分的首部，反转链表部分剩余节点依旧保持相对顺序（头插法）；
比如1->2->3->4->5,m=1,n=5；
第一次反转：1(head) 2(next) 3 4 5 反转为 2 1 3 4 5
第二次反转：2 1(head) 3(next) 4 5 反转为 3 2 1 4 5
第三次发转：3 2 1(head) 4(next) 5 反转为 4 3 2 1 5
第四次反转：4 3 2 1(head) 5(next) 反转为 5 4 3 2 1
3、Java 代码
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
for(int i = 1; i < m; i++){
pre = pre.next;
}
head = pre.next;
for(int i = m; i < n; i++){
ListNode nex = head.next;
head.next = nex.next;
nex.next = pre.next;
pre.next = nex;
}
return dummy.next;
}
}
参考文章：
https://leetcode.cn/problems/reverse-linked-list-ii/comments/
