每天一道leetcode92-反转m到n处的链表

• 2019 年 10 月 4 日
• 筆記

题目

每天一道leetcode92-反转m到n处的链表 分类：链表 中文链接： https://leetcode-cn.com/problems/reverse-linked-list-ii/ 英文链接 https://leetcode.com/problems/reverse-linked-list-ii/

题目详述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。 说明: 1 ≤ m ≤ n ≤ 链表长度。 示例: 输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL

题目详解

思路

• 分两种情况讨论哈，一种是m等于1的，一种是m不等于1的
• m等于1的话，简单，就是一个反转链表，如何反转见这篇文章，之前写过；m等于1的话，先反转m-n这些节点，反转完成以后，一开始的头结点就成了最后一个节点，所以反转前把这个节点保留下来，然后反转结束以后把后面的连起来就行；
• m不等于1的话，说明是反转的中间部分的这些节点，

代码

/**   * Definition for singly-linked list.   * public class ListNode {   *     int val;   *     ListNode next;   *     ListNode(int x) { val = x; }   * }   */  class Solution {      public ListNode reverseBetween(ListNode head, int m, int n) {          if(head == null || head.next == null)              return head;          if(m != 1)          {              ListNode temp = head.next;              ListNode preFirst = head;//指向反转处的前一个节点值              for(int i=0;i<m-2;i++)              {                  temp = temp.next;                  preFirst = preFirst.next;              }              //从temp处开始反转链表；              //由于temp是反转后的最后一个节点记录temp这个节点              ListNode last = temp;              ListNode pre = temp;//在这里开始反转链表 老套路              ListNode pNode = temp.next;              ListNode next = null;              for(int i=0;i<n-m;i++)              {                  next = pNode.next;                  pNode.next = pre;                  pre = pNode;                  pNode = next;              }              preFirst.next = pre;              last.next = pNode;          }else{              ListNode pre = head;              ListNode pNode = head.next;              ListNode next = null;              ListNode last = pre;//记录下来这个last节点；              for(int i=0;i<n-m;i++)              {                  next = pNode.next;                  pNode.next = pre;                  pre = pNode;                  pNode = next;              }              last.next = pNode;//反转后的最后一个节点连接上后续的节点              return pre;//pre是反转后的头结点；          }          return head;      }  }  

代码讲解

• 15-16行，一个temp是反转节点的开始的第一个，preFirst是temp节点的前一个节点，用来最后连接使用；
• 17-21行 因为是从第m个节点开始，所以先去找到这个第m个节点；
• 24-34行 就是反转链表了，不懂的看这篇文章，其中要注意的是，要把反转之前的第一个节点也就是m所在的节点保留下来，这样方便最后连接没反转的后一段部分的节点；
• 35-36行 就是连接反转部分节点与前后两部分节点
• 38-50行 就是反转前1-n个节点的代码，反转链表看之前的链接，然后需要注意的就是把第一个节点保留下来用来连接。