题目

image.png

思路

  • 思路一：找到第m - 1个节点，以其为起点，对m~n节点使用头插法插入到第m个节点的后面

  • 思路二：使用递归找到m - 1各节点，然后再反转链表关键在反转链表的时候记录n+1的节点，head.next = successor确保反转后的链表指向后续未反转的链表

    代码

    1.   //1. 迭代
    2.   public ListNode reverseBetween(ListNode head, int m, int n) {
    3.       ListNode dummy = new ListNode(0);
    4.       dummy.next = head;
    5.       ListNode pre = dummy;
    6.       for (int i = 1; i < m; i++) {
    7.           pre = pre.next;
    8.       }
    9.       head = pre.next;
    10.       //以第m个节点为起点，使用头插法插入m~n的节点
    11.       for (int i = m; i < n; i++) {
    12.           ListNode next = head.next;
    13.           head.next = next.next;
    14.           next.next = pre.next;
    15.           pre.next = next;
    16.       }
    17.       return dummy.next;
    18.   }
    20.   //2. 递归
    21.   ListNode successor = null;
    22.   public ListNode reverseBetween(ListNode head, int m, int n) {
    23.       if (m == 1) {
    24.           return reverseN(head, n);
    25.       }
    26.       head.next = reverseBetween(head.next, m - 1, n - 1);
    27.       return head;
    28.   }
    30.   public ListNode reverseN(ListNode head, int m) {
    31.       if (m == 1) {
    32.           successor = head.next;
    33.           return head;
    34.       }
    35.       ListNode nHead = reverseN(head.next, m - 1);
    36.       head.next.next = head;
    37.       head.next = successor;
    38.       return nHead;
    39.   }

    反转链表II