image.png

解题思路

迭代

image.png

  • 使用虚拟头节点来统一第一个元素的操作
  • pre指针向后走m-1步到达需要反转的第一个节点的pre节点
  • cur就是此时需要反转的
  • tmp记录cur此时的next元素
  • 首先让cur的next指针指向tmp.next
  • 然后让tmp指向cur的前面
  • 再将pre.next指向tmp
  1. public ListNode reverseBetween(ListNode head, int m, int n) {
  2.         //建立一个虚拟头结点
  3.         ListNode dummyHead = new ListNode(-1);
  4.         //虚拟头结点的next指向head
  5.         dummyHead.next = head;
  6.         //pre的next指向head
  7.         ListNode pre = dummyHead;
  8.         //pre向后移动m-1步
  9.         for(int i=0;i<m-1;i++)
  10.             pre=pre.next;
  11.         //记录当前要修改的值
  12.         ListNode cur = pre.next;
  13.         for(int i=m;i<n;i++){
  14.             //记录临时指针
  15.             ListNode tmp = cur.next;
  16.             cur.next = tmp.next;          
  17.             tmp.next = pre.next;
  18.             pre.next = tmp;
  19.         }
  20.         return dummyHead.next;
  21.     }