牛客网高频算法题系列-BM2-链表内指定区间反转

题目描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)，空间复杂度 O(1)。

原题目见：BM2 链表内指定区间反转

解法一：链表遍历，指针交换

因为起始位置可能是头结点，所以首先设置一个虚拟的头结点dummyNode并将next指向原有的头结点，然后处理过程如下：

  • 首先遍历链表，找到起始位置m的前一个结点pre，用来记录反转前的结点；
  • 然后用cur和next记录pre的next结点，用next记录cur的next结点；
  • 然后继续遍历链表，通过交换pre、next、cur的next指针，将next结点转到pre结点的下一个结点处，然后循环处理cur的下一个结点；
  • 遍历到结束结束位置n的结点即反转结束。
  • 最后，返回dummyNode结点的next结点即为反转后的链表。
  1. public class Bm002 {
  2.     /**
  3.      * @param head ListNode类
  4.      * @param m    起始位置
  5.      * @param n    结束位置
  6.      * @return ListNode类
  7.      */
  8.     public static ListNode reverseBetween(ListNode head, int m, int n) {
  9.         if (head == null || head.next == null) {
  10.             return head;
  11.         }
  12.         if (m == n) {
  13.             return head;
  14.         }
  15.         // 设置虚拟头结点
  16.         ListNode dummyNode = new ListNode(-1);
  17.         dummyNode.next = head;
  18.         // pre为反转区间的前一个结点
  19.         ListNode pre = dummyNode;
  20.         for (int i = 0; i < m - 1; i++) {
  21.             pre = pre.next;
  22.         }
  23.         // cur初始为反转区间的起始结点
  24.         ListNode cur = pre.next;
  25.         ListNode next;
  26.         for (int i = 0; i < n - m; i++) {
  27.             // 通过交换next指针指向，将next结点转到pre结点的下一个结点处
  28.             next = cur.next;
  29.             cur.next = next.next;
  30.             next.next = pre.next;
  31.             pre.next = next;
  32.         }
  34.         // 最后，返回dummyNode结点的next结点即为反转后的链表
  35.         return dummyNode.next;
  36.     }
  38.     public static void main(String[] args) {
  39.         ListNode head = ListNode.testCase2();
  40.         System.out.println("指定区间反转之前");
  41.         ListNode.print(head);
  43.         ListNode newHead = reverseBetween(head, 2, 4);
  44.         System.out.println("指定区间反转之后");
  45.         ListNode.print(newHead);
  46.     }
  47. }

牛客网高频算法题系列-BM2-链表内指定区间反转 - 图1
牛客网高频算法题系列-BM2-链表内指定区间反转 - 图2
相信坚持的力量！