网站主题及样式优化,个人网站 可以做论坛吗,软件开发包括,最容易做流量的网站给你单链表的头指针 head 和两个整数 left 和 right #xff0c;其中 left right 。请你反转从位置 left 到位置 right 的链表节点#xff0c;返回 反转后的链表 。 示例 1#xff1a; 输入#xff1a;head [1,2,3,4,5], left 2, right 4
输出#xff1a;[1,4,3,2…
给你单链表的头指针 head 和两个整数 left 和 right 其中 left right 。请你反转从位置 left 到位置 right 的链表节点返回 反转后的链表 。 示例 1 输入head [1,2,3,4,5], left 2, right 4
输出[1,4,3,2,5]示例 2
输入head [5], left 1, right 1
输出[5]提示
链表中节点数目为 n1 n 500-500 Node.val 5001 left right n 解法一
首先找到 m 的位置记录两端的节点 left1 和 left2 。
然后每遍历一个节点就倒置一个节点。
到 n 的位置后利用之前的 left1 和 left2 完成连接。
为了完成链表的倒置需要两个指针 pre 和 head。为了少考虑边界条件例如 m 1 的倒置。加一个哨兵节点 dummy。
m 2, n 41 2 3 4 5 加入哨兵节点 dpre 简写 phead 简写 h0 1 2 3 4 5 往后遍历
^ ^
d h
p0 1 2 3 4 5 此时 h 指向 m 的位置记录 p 和 h 为 l1 和 l2
^ ^ ^
d p h0 1 2 3 4 5 然后继续遍历
^ ^ ^
d p hl1 l20 1 2 3 4 5 开始倒置链表使得 h 指向 p
^ ^ ^ ^
d l1 p hl2当前状态用图形描述 倒转链表将 h 的 next 指向 p并且后移 p 和 h。 然后上边一步会重复多次直到 h 到达 n 的位置。当然这道题比较特殊上图 h 已经到达了 n 的位置。
此时我们需要将 h 指向 p同时将 l1 指向 hl2 指向 h.next使得链表接起来。 操作完成将 dummy.next 返回即可。
public ListNode reverseBetween(ListNode head, int m, int n) {if (m n) {return head;}ListNode dummy new ListNode(0);dummy.next head;int count 0;ListNode left1 null;ListNode left2 null;ListNode pre dummy;while (head ! null) {count;//到达 m保存 l1 和 l2if (count m) {left1 pre;left2 head;}// m 和 n 之间倒转链表if (count m count n) {ListNode temp head.next;head.next pre;pre head;head temp;continue;}//到达 nif (count n) {left2.next head.next;head.next pre;left1.next head;break;}//两个指针后移head head.next;pre pre.next;}return dummy.next;
}时间复杂度On。
空间复杂度O1。
