一、知识点:
链表、链表反转
二、文字分析:
- 创建一个虚拟头节点
dummy,将其指向原链表的头节点head。 - 定位到需要反转的起始位置的前一个节点,即第
left - 1个节点。 - 在反转区间内,逐个将节点插入到起始位置的前面,直到达到右边界。
- 将反转区间内的最后一个节点的
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;
}
}

京公网安备 11010502036488号