链表｜ Leetcode 92

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/