LeetCode92 反转链表II
题目
给你单链表的头指针 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
进阶： 你可以使用一趟扫描完成反转吗？
方法
穿针引线法
现找到反转的头节点，然后用常规的反转链表法反转后再连接
- 时间复杂度：O（n）,n为链表节点个数
- 时间复杂度：O（1）
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode newHead = new ListNode();
newHead.next = head;
ListNode pre = newHead;
int i = 1;
while(i头插法
遍历需要反转的链表节点，将每个节点放入头节点的位置达到反转的效果
头插法首先定义cur为需要反转的头节点，pre为需要反转的前一个节点，这两个节点不变，然后执行以下步骤：
- 取next为cur的下一个节点
- 将cur指向next的下一个节点
- 将next指向pre的下一个节点
- 将pre指向next
- 时间复杂度：O（n）,n为链表节点个数
- 时间复杂度：O（1）
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode newHead = new ListNode();
newHead.next = head;
ListNode pre = newHead;
for(int i=0;i