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

链表内指定区间反转

https://www.nowcoder.com/practice/b58434e200a648c589ca2063f1faf58c

解法一：区间部分前驱插入

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) {
        if (head == null || head.next == null || m == n) {
            return head;
        }
        // find sublist from m to n
        ListNode headOfSubList = head;
        ListNode endOfSubList = head;
        ListNode prevOfInsert = new ListNode(-1);
        prevOfInsert.next = head;
        int i = 1;
        int j = 1;
        while (i < m) {
            i++;
            prevOfInsert = prevOfInsert.next;
            headOfSubList = headOfSubList.next;
        }

        while (j < n) {
            j++;
            endOfSubList = endOfSubList.next;
        }

        ListNode nextOfInsert = endOfSubList.next;
        // exclude sub list from original list
        prevOfInsert.next = nextOfInsert;
        endOfSubList.next = null;
        // insert sub list to original list
        ListNode toBeInsert = null;
        while (headOfSubList != null) {
            toBeInsert = headOfSubList;
            headOfSubList = headOfSubList.next;
            // insert first node of sub list to original list
            toBeInsert.next = nextOfInsert;
            prevOfInsert.next = toBeInsert;
            nextOfInsert = toBeInsert;
        }
        // if m == 1, then "toBeInsert" is the first node of the list
        if (m == 1) {
            return toBeInsert;
        }
        return head;
    }
}

1.1.解题思路：

先找到需要反转的区间，同时标记区间前后的两个节点
将需要反转的区间从原链表中分离
把需要反转的区间逐个倒着插入原来的链表

1.2.解题图解：

1.先找到需要反转的区间，同时标记区间前后的两个节点，也就是4个节点

2.将需要反转的区间从原链表中分离

3.把需要反转的区间逐个倒着插入原来的链表

3.1先Sublist中的第一个节点

3.2插入作为endOfSubList的前驱节点

3.3将nextOfInsert节点重新赋值，那么下一个节点就将插入在1和2之间

3.4完成sublist为空，停止循环

1.3.Corner case

1. m = n or head is null or list have only one node

  if (head == null || head.next == null || m == n) {
      return head;
  }

2.node m is the head node

        if (m == 1) {
            return toBeInsert;
        }

其他情况，比如list have only two node or list have more that 2 nodes or node n is the last node都能被代码覆盖，不属于corner case

解法二：借助栈

import java.util.*;

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

public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {
        if (head == null || head.next == null || m == n) {
            return head;
        }
        // find Node n, and push nodes from m to n to stack
        ListNode nNode = head;
        ListNode prevOfInsert = new ListNode(-1);
        prevOfInsert.next = head;
        int i = 1;
        int j = m;
        while (i < m) {
            i++;
            prevOfInsert = prevOfInsert.next;
            nNode = nNode.next;
        }

        Stack<ListNode> backup = new Stack<ListNode>();
        while (j < n) {
            j++;
            backup.push(nNode);
            nNode = nNode.next;
        }
        backup.push(nNode);
        ListNode nextOfInsert = nNode.next;
        // exclude sub list from original list
        prevOfInsert.next = nextOfInsert;
        nNode.next = null;
        // insert elements from stack to original list
        ListNode toBeInsert = null;
        while (!backup.empty()) {
            toBeInsert = backup.pop();
            toBeInsert.next = nextOfInsert;
            prevOfInsert.next = toBeInsert;
            prevOfInsert = toBeInsert;
        }
        // if m == 1, then "nNode" is the last node of original sublist, also the first node of the reversed list
        if (m == 1) {
            return nNode;
        }
        return head;
    }
}