🌗 92. 反转链表 II

难度: 🌗

问题描述

---

解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 思路：
        // 找到要反转链表区间，切分，反转，合并
        if(left == right) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        for(int i = 1; i < left; i ++) {
            pre = cur;
            cur = cur.next;
        }
        // 反转链表
        if(pre != null) {
            pre.next = null;
        }
        ListNode tmp = reverse(cur, right - left + 1);
        if(pre != null) {
            pre.next = tmp;
        } else {
            return tmp;
        }
        return head;
    }

    private ListNode reverse(ListNode head, int len) {
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        for(int i = 0; i < len; i ++) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        head.next = next;
        return pre;
    }
}

---

输出