做本题之前要把反转链表做熟来。
两个思路:
思路一:模拟
直接在m的前一个节点和n的后一个节点做上标记,然后将链表断开,将n-m的节点反转后,在连接对应的节点,返回结果。思路比较好想,细节比较多,需要注意。
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 dummyNode=new ListNode(-1); dummyNode.next=head; ListNode pre=dummyNode; //pre结点走到m的前一个结点 for(int i=0;i<m-1;i++){ pre=pre.next; } //rightnode走到n的结点 ListNode rigthNode =pre; for(int i=0;i<n-m+1;i++){ rigthNode=rigthNode.next; } ListNode leftNode = pre.next; ListNode cur = rigthNode.next; pre.next=null; rigthNode.next=null; reverse(leftNode); pre.next=rigthNode; leftNode.next=cur; return dummyNode.next; } public void reverse (ListNode head) { if(head==null) return; ListNode pre =null; ListNode cur=head; while(cur!=null){ ListNode next=cur.next; cur.next=pre; pre=cur; cur=next; } } }
思路二:该思路借鉴其他牛友的答案。
对于reverse部分有点迷糊。网上看到的解释,也许更能帮助理解.https://yq.aliyun.com/articles/3867
不妨拿出四本书,摞成一摞(自上而下为 A B C D),要让这四本书的位置完全颠倒过来(即自上而下为 D C B A):
盯住书A,每次操作把A下面的那本书放到最上面
初始位置:自上而下为 A B C D
第一次操作后:自上而下为 B A C D
第二次操作后:自上而下为 C B A D
第三次操作后:自上而下为 D C B A
不妨拿出四本书,摞成一摞(自上而下为 A B C D),要让这四本书的位置完全颠倒过来(即自上而下为 D C B A):
盯住书A,每次操作把A下面的那本书放到最上面
初始位置:自上而下为 A B C D
第一次操作后:自上而下为 B A C D
第二次操作后:自上而下为 C B A D
第三次操作后:自上而下为 D C B A
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 preStart=pre; ListNode start=head; for(int i=0;i<m-1;i++){ preStart=preStart.next; start=start.next; } for(int i=0;i<n-m;i++){ ListNode temp=start.next; start.next=temp.next; temp.next=preStart.next; preStart.next=temp; } return pre.next; } }拿一开始的例子来测试。
首先,{1,2,3,4,5}2,4
preStart=1,start=2,j经过一次reverse后变成{1,3,2,4,5},再一次{1,4,3,2,5},完成。每次只要把2的下一位往最上面放就好了。思路很棒。