一、知识点:

链表、链表反转

二、文字分析:

  1. 创建一个虚拟头节点dummy,将其指向原链表的头节点head
  2. 定位到需要反转的起始位置的前一个节点,即第left - 1个节点。
  3. 在反转区间内,逐个将节点插入到起始位置的前面,直到达到右边界。
  4. 将反转区间内的最后一个节点的next指向剩余部分的第一个节点。

只需对链表进行一次遍历,因此时间复杂度为O(n),其中n是链表的长度。由于只使用了常数级别的额外空间,因此空间复杂度为O(1)。

三、编程语言:

java

四、正确代码:

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;  // 虚拟头节点

        ListNode pre = dummy;  // 反转区间的前一个节点
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }

        ListNode cur = pre.next;  // 反转区间的当前节点
        ListNode reverseHead = null;  // 反转区间的头节点

        for (int i = 0; i < right - left + 1; i++) {
            ListNode next = cur.next;  // 下一个节点

            // 反转节点
            cur.next = reverseHead;
            reverseHead = cur;

            cur = next;
        }

        // 连接反转后的链表
        pre.next.next = cur;
        pre.next = reverseHead;

        return dummy.next;
    }
}