Leetcode 分類刷題 —— 鏈表類（Linked List）

1、題目

Leetcode 92. Reverse Linked List II

給你單鏈表的頭指針 head 和兩個整數 left 和 right ，其中 left <= right 。請你反轉從位置 left 到位置 right 的鏈表節(jié)點，返回 反轉后的鏈表 。

2、思路

思路：head表示需要反轉的頭節(jié)點，pre表示需要反轉頭節(jié)點的前驅節(jié)點
我們不斷地將head的next節(jié)點移動到需要反轉鏈表部分的首部，反轉鏈表部分剩余節(jié)點依舊保持相對順序（頭插法）；
比如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
第三次發(fā)轉：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/