链表内指定区间反转

前面已经分析了，对整个链表的反转。这里原理类似，就是先确定要反转的位置，定义为子链表，对子链表进行全局反转，然后拼接链表即可。关键点有以下几个：

找点需要反转的位置
反转前要将子链表断开，对断开的子链表进行反转
要先记录原来链表的位置，确保后续链表能完整拼接成整个链表

如图一所示，记录了一些链表的指针，以m=2，n=4为例。反转链表然后拼接，图中虚线表示要断开的链表。

图一

首先需要创建一个虚拟链表头结点（VHeader），这个头结点，用于确定子链表的位置。

虚拟头结点的创建

ListNode VHeader = new ListNode(-1)
//让它指向真正的头
 VHeader.next = head;
//此时的pre先定义到虚拟头这里，后面会通过循环找到真正的pre
ListNode pre = VHeader;

pre的正确位置就是子链表头的前一个位置，这里子链表m=2,前一个位置就是m-1

for(i = 0; i < m-1; i++){
	pre = pre.next;
}

接着需要确认子链表的长度，然后断开前后形成一个子链表，由我们初中学过的数学知识知道，链表长度=n-m+1

//初始链表长度为pre的位置
ListNode right = pre;
//链表长度
for(j = 0; j < n-m+1; j++){
	right = right.next; 
}

定义子链表头结点，然后断开链表

//子链表头结点
ListNode left = pre.next;
//断开链表
//断开前先保存一下链表前后的值，方便后面连接链表
ListNode cur = right.next;
right.next = null;
pre.next = null;

对断开的子链表进行链表反转。(全局反转)这个不再赘述：https://www.nowcoder.com/discuss/453360542908940288

public void ReverseList(ListNode head){
  ListNode pre = null;
  ListNode cur = head;
  while(cur != null){
	ListNode temp = cur.next;
	cur.next = pre;
	pre = cur;
	cur = temp;
  }
}

最后一步拼接整个链表。

pre.next = right;
left.next = cur;//之前已经保存，目的就是在这里拼接
//最后返回VHeader.next即可

完整代码：

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        //初始化虚拟头结点
        ListNode vHeader = new ListNode(-1);
        vHeader.next = head;
        ListNode pre = vHeader;
        //遍历找到pre的正确位置
        for(int i = 0; i < m-1; i++){
            pre = pre.next;
        }
        //定义子链表
        ListNode right = pre;
        for(int j = 0; j < n-m+1; j++){
            right = right.next;
        }
        //取子链表的头
        ListNode left = pre.next;
        //断开子链表
        ListNode cur = right.next;
        right.next = null;
        pre.next = null;
        //子链表反转
        ReverseList(left);
        //拼接链表
        pre.next = right;
        left.next = cur; 
        return vHeader.next;

}
    public void ReverseList(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
    }
}

欢迎大家批评指点。

题解 | #链表内指定区间反转#

链表内指定区间反转

全站热榜