区间反转问题解析》"/>
《算法通关村第二关——指定区间反转问题解析》
《算法通关村第二关——指定区间反转问题解析》
题目描述
给你单链表的头指针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;}}
近期在自学 Java 做项目,加入了一个编程学习圈子,里面有编程学习路线和原创的项目教程,感觉非常不错。还可以 1 对 1 和大厂嘉宾交流答疑,也希望能对大家有帮助,扫 ⬇️ 二维码即可加入。
也可以点击链接:我正在「编程导航」和朋友们讨论有趣的话题,你⼀起来吧?
更多推荐
《算法通关村第二关——指定区间反转问题解析》
发布评论