1. package top.ssyuan.medium;
    3. import java.util.Stack;
    5. import top.ssyuan.Util;
    6. import top.ssyuan.easy.Lesson206;
    8. /**
    9.  * 92. Reverse Linked List II
    10.  * Medium
    11.  * <p>
    12.  * Given the head of a singly linked list and two integers left and right where left <= right,
    13.  * reverse the nodes of the list from position left to position right, and return the reversed list.
    14.  * <p>
    15.  * <p>
    16.  * Example 1:
    17.  * <p>
    18.  * <p>
    19.  * Input: head = [1,2,3,4,5], left = 2, right = 4
    20.  * Output: [1,4,3,2,5]
    21.  * Example 2:
    22.  * <p>
    23.  * Input: head = [5], left = 1, right = 1
    24.  * Output: [5]
    25.  * <p>
    26.  * <p>
    27.  * Constraints:
    28.  * <p>
    29.  * The number of nodes in the list is n.
    30.  * 1 <= n <= 500
    31.  * -500 <= Node.val <= 500
    32.  * 1 <= left <= right <= n
    33.  */
    34. public class Lesson92 {
    37.     public static void main(String[] args) {
    38.         Lesson92 lesson = new Lesson92();
    39.         ListNode head = lesson.genLinkList(10);
    40.         lesson.printLink(head);
    41.         head = new Solution1().reverseBetween(head, 1, 3);
    42.         Util.println("");
    43.         lesson.printLink(head);
    44.     }
    46.     private void printLink(ListNode head) {
    47.         ListNode node = head;
    48.         while (node != null) {
    49.             Util.print(node.val + "->");
    50.             node = node.next;
    51.         }
    52.     }
    54.     private ListNode genLinkList(int count) {
    55.         if (count < 1) return null;
    57.         ListNode head = new ListNode((int) (Math.random() * 100));
    58.         ListNode curNode = head;
    59.         for (int i = 1; i < count; i++) {
    60.             curNode.next = new ListNode((int) (Math.random() * 100));
    61.             curNode = curNode.next;
    62.         }
    64.         return head;
    65.     }
    68.     //Definition for singly-linked list.
    69.     private class ListNode {
    70.         int val;
    71.         ListNode next;
    73.         ListNode() {
    74.         }
    76.         ListNode(int val) {
    77.             this.val = val;
    78.         }
    80.         ListNode(int val, ListNode next) {
    81.             this.val = val;
    82.             this.next = next;
    83.         }
    84.     }
    86.     private static class Solution1 {
    88.         public ListNode reverseBetween(ListNode head, int left, int right) {
    89.             if (head == null || left > right) {
    90.                 return null;
    91.             }
    93.             Stack<ListNode> stack = new Stack<>();
    94.             ListNode node = head;
    95.             ListNode pre  = head;
    96.             ListNode next = null;
    98.             int index = 0;
    99.             while (node != null) {
    100.                 if (index < left - 1) {
    101.                     pre = node;
    102.                 }
    103.                 if (index >= left - 1 && index < right) {
    104.                     stack.push(node);
    105.                 }
    106.                 if (index >= right) {
    107.                     next = node;
    108.                     break;
    109.                 }
    110.                 node = node.next;
    111.                 index++;
    112.             }
    114.             ListNode head2 = stack.pop();
    115.             node = head2;
    116.             while (!stack.empty()) {
    117.                 node.next = stack.pop();
    118.                 node = node.next;
    119.             }
    121.             pre.next = head2;
    123.             if (node != null) {
    124.                 node.next = next;
    125.             }
    127.             return left == 1 ? head2 : head;
    128.         }
    129.     }
    131.     private static class Solution2 {
    133.         public ListNode reverseBetween(ListNode head, int left, int right) {
    134.             if (head == null || left >= right) {
    135.                 return null;
    136.             }
    138.             ListNode node = head;
    139.             ListNode pre = null;
    140.             ListNode tmp = node;
    141.             while (node != null) {
    142.                 tmp = node;
    143.                 node = node.next;
    144.                 tmp.next = pre;
    145.                 pre = tmp;
    146.             }
    148.             return tmp;
    149.         }
    150.     }
    152. }