一、知识点:
链表、链表反转
二、文字分析:
- 创建一个虚拟头节点
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; } }