2021.3.18
https://leetcode-cn.com/problems/reverse-linked-list-ii/

题目

给你单链表的头节点 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

反转链表Ⅱ - 图1

  1. 输入：head = [1,2,3,4,5], left = 2, right = 4
  2. 输出：[1,4,3,2,5]
  4. 输入：head = [5], left = 1, right = 1
  5. 输出：[5]

提示：

  • 链表中节点数目为 n
  • 1 <= n <= 500
  • -500 <= Node.val <= 500

  • 1 <= left <= right <= n

    思路

  • 一趟扫描完成。防止从第一个节点开始翻转的特殊情况，建立哨兵节点（给head节点加一个父亲father）。

  • 然后找到left位置的节点，将left位置节点的父亲记录下来，开始寻找right。
  • 将left到right看作一条单独的链，left是链尾tail，right是链头head2，开始链尾链头都是left位置的节点。
  • 然后遍历下一个节点t，将其加入单独链中，此时该节点为链头，它的next指向之前的链头。
  • 如果该节点的位置正好是right，则单独链的翻转已经完成，将其加入整条链中，单独链的链尾的next指向right位置节点的next，父亲节点的next指向right位置节点，链表反转完成。
  • 此时新链的head为哨兵节点的next值。

    AC代码

    1. /**
    2. * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
    3. * 内存消耗：35.9 MB, 在所有 Java 提交中击败了83.90%的用户
    4. */
    5. public ListNode reverseBetween(ListNode head, int left, int right) {
    6.   // 位置相等不用翻转直接返回head节点
    7.   if (left == right) {
    8.       return head;
    9.   }
    10.   // 建立哨兵节点
    11.   ListNode sentry = new ListNode(0, head);    
    12.   // 寻找left位置的节点
    13.   ListNode leftNode = sentry;
    14.   ListNode father = null;
    15.   int count = 0;
    16.   while (leftNode.next != null) {
    17.       ListNode node = leftNode.next;
    18.       count++;
    19.       if (count == left) {
    20.           // 记录left位置节点的父亲
    21.           father = leftNode;
    22.           leftNode = node;
    23.           break;
    24.       }
    25.       leftNode = node;
    26.   }
    27.   // 翻转left-right之间的链表
    28.   ListNode tail = leftNode, head2 = leftNode, node = leftNode.next;
    29.   while (node != null) {
    30.       count++;
    31.       // 找到right位置
    32.       if (count == right) {
    33.           ListNode next = node.next;
    34.           node.next = head2;
    35.           tail.next = next;
    36.           father.next = node;
    37.           break;
    38.       }
    39.       ListNode next = node.next;
    40.       node.next = head2;
    41.       head2 = node;
    42.       node = next;
    43.   }
    44.   // 返回哨兵节点的next，为新链的链头
    45.   return sentry.next;
    46. }