鸿铭物流网络建站,北京网站建设 公司,wordpress登录之后强制绑定邮箱,搭建网站代码链表定区间翻转链表 题目链接题目描述核心思想详细图解代码实现复杂度分析 题目链接
链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com)
题目描述 核心思想
遍历链表的过程中在进行原地翻转
[m,n]翻转区间记作子链表,找到子链表的 起始节点 left 和 终止节点 right记录在… 链表定区间翻转链表 题目链接题目描述核心思想详细图解代码实现复杂度分析 题目链接
链表内指定区间反转_牛客题霸_牛客网 (nowcoder.com)
题目描述 核心思想
遍历链表的过程中在进行原地翻转
[m,n]翻转区间记作子链表,找到子链表的 起始节点 left 和 终止节点 right记录在链表中 子链表起始节点的前驱节点 leftPre 和子链表 终止节点的后继结点 rightNext对子链表进行反转处理后与leftPre 和rightNext重新相连为了防止头结点 head 的多种情况的讨论,选择 另声明一个虚拟头结点 newHead 作为遍历的起点 详细图解
按图索骥 开始头插 头插结束 子链表重新链接 代码实现
import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** param head ListNode类* param m int整型* param n int整型* return ListNode类*///我们把[m,n]之间的节点当做是子链表public ListNode reverseBetween(ListNode head, int m, int n) {//虚拟头结点ListNode newHead new ListNode(-1);newHead.next head;//把虚拟头结点连入链表中//找到子链表的起始节点left和终止节点right(要求记录下左子链表左节点的前驱节点)ListNode leftPre newHead;while (m 1) {leftPre leftPre.next;m--;}//while结束之后保留的leftPre即起始节点的前驱结点ListNode left leftPre.next;//子链表的起始节点ListNode right newHead;while (n 0) {right right.next;n--;}ListNode rightNext right.next;//保留的rightNext即终止节点的后继结点//子链表进行头插ListNode subHead left;//子链表的头结点ListNode cur subHead.next;while (cur ! rightNext) {ListNode curNext cur.next;cur.next subHead;subHead cur;cur curNext;}//开始链接子链表leftPre.next subHead;left.next rightNext;return newHead.next;//返回链表原头结点}static class ListNode {int val;ListNode next null;public ListNode(int val) {this.val val;}}
}复杂度分析 时间复杂度 O(N) ,最坏情况下需要遍历整个链表 空间复杂度 O(1) ,使用到常数个变量
