当前位置：首页 > news >正文

《算法通关村第二关——指定区间反转问题解析》

news 2025/7/31 19:12:03

《算法通关村第二关——指定区间反转问题解析》

题目描述

给你单链表的头指针head和两个整数left和right，其中left <= right 。请你反转从位置left到位置right的链表节点，返回反转后的链表。

示例1：
输入： head = [1,2,3,4,5],left = 2, right = 4
输出： [1,4,3,2,5]

头插法

通过一个一个插入前面进行反转。

在这里插入图片描述

代码：

/*** 头插法指定区间反转* @param head* @param start就是题中的left* @param end 题中的right* @return*/
public static LinkedNode ReverseSpecificInterval1(LinkedNode head , int start,int end){// 设置dummyNode 是这类问题的一般解法LinkedNode dummyNode = new LinkedNode(-1);dummyNode.setNext(head);LinkedNode pre = dummyNode;for(int i = 0 ; i < start - 1 ; i++){pre = pre.getNext();}LinkedNode cur = pre.getNext();LinkedNode next = null;for(int i = 0 ;i < end-start ; i++){next = cur.getNext();cur.setNext(next.getNext());next.setNext(pre.getNext());pre.setNext(next);}return dummyNode.getNext();
}

穿针引线法

通过把指定区间提取出来，然后进行反转，最后再接回原链表的方法。

在这里插入图片描述

上代码：

/*** 穿针引线* @param head* @param start* @param end* @return*/public static LinkedNode ReverseSpecificInterval2(LinkedNode head,int start , int end){// 因为头节点可能发生变化，使用虚拟头节点可以便面复杂的分类讨论LinkedNode dummyNode = new LinkedNode(-1);dummyNode.setNext(head);LinkedNode pre = dummyNode;// 第一步，从虚拟头节点走start-1步，来到start节点的前一个结点。for ( int i = 0 ; i < start -1 ; i++){pre = pre.getNext();}// 第二步，从pre 再走end-start+1步来到end节点LinkedNode endNode = pre;for(int i = 0 ; i  < end-start+1 ; i++){endNode = endNode.getNext();}// 第三步切出一个子链LinkedNode startNode = pre.getNext();LinkedNode succ = endNode.getNext();endNode.setNext(null);// 第四步反转链表reverseLinkedList(startNode);// 第五步，接回原来的链表pre.setNext(endNode);startNode.setNext(succ);return dummyNode.getNext();}private static void reverseLinkedList(LinkedNode startNode) {LinkedNode pre = null ;LinkedNode cur = startNode;while(cur != null){LinkedNode next = cur.getNext();cur.setNext(pre);pre = cur;cur = next;}}