import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ public ListNode reverseBetween (ListNode head, int m, int n) { // write code here ListNode pre = new ListNode(-1); pre.next = head; ListNode newList = pre; //前面是不需要反转的节点的遍历 for(int i = 1; i < m; i++){ pre = head; head = head.next; } //下面是需要反转的节点,记录开始位置和第一个反转点(因为这个点事反转的最后一个点),需要这个点衔接后面不反转的点 ListNode mid = pre; ListNode midRight = head; for(int i = m; i<= n; i++){ ListNode tmp = head.next; mid.next = head; midRight.next = head.next; if(pre != mid){ //避免循环 head.next = pre; } pre = head; head = tmp; } return newList.next; } }
mid和midRight 的位置不动,head和pre相邻向前移动。mid的next和midRight的next向后移动,注意避免循环
另一种相似解法
import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ public ListNode reverseBetween (ListNode head, int m, int n) { //加个表头 ListNode newList = new ListNode(-1); newList.next = head; //前序节点 ListNode pre = newList; //找到m for(int i = 1; i < m; i++){ pre = head; head = head.next; } //从m反转到n for(int i = m; i < n; i++){ ListNode temp = head.next; head.next = temp.next; temp.next = pre.next; pre.next = temp; } //返回去掉表头 return newList.next; } }
与方法1的区别在于反转的方式不一样
方法1引入了mid和midRight固定开始反转的位置和第一个反转的点,pre和head是相邻向前移动。
方法2中pre和head的位置是固定的,相当于方法1中的mid和midRight。不断移动pre的next和head的next