【LeetCode92】Reverse Linked List II★★

题目描述：

解题思路：

　　题目大意：给定一个链表，反转第m到第n个结点部分，m、n满足1 ≤ m ≤ n ≤ length of list。

　　解题思路参照LeetCode206题，用迭代法，不过要注意以下几点：

　　（a）：为方便操作，新建一个辅助结点dummy，使其下一个结点指向头节点。

　　（b）：维护4个指针：pre、current、then、then_next，pre指向第m个结点的前一个结点，current指向当前操作的位于区间[m，n]的结点，then指向current的下一个结点，then_next指向then的下一个结点。

　　注意：这里的current、then、then_next就相当于LeetCode206题中的pre、current、next！

　　初始化状态如下：

　　dummy.next=head;

　　pre=dummy;

　　current=null,then=null,then_next=null。

　　下面以链表1->2->3->4->5，m=2，n=4举例：

　　（1）初始状态：

　　（2）遍历到m位置时：

　　（3）一次迭代操作后：

　　（4）迭代最终位置：

　　　　(5)执行①pre.next.next=then;②pre.next=current; 后：

Java代码：

 //public class LeetCode92为测试

 public class LeetCode92 {

     public static void main(String[] args) {

         ListNode n1=new ListNode(1),n2=new ListNode(2),n3=new ListNode(3),n4=new ListNode(4),n5=new ListNode(5);

         n1.next=n2;

         n2.next=n3;

         n3.next=n4;

         n4.next=n5;

         System.out.println("原来链表:"+n1.val+"->"+n2.val+"->"+n3.val+"->"+n4.val+"->"+n5.val);

         ListNode n=new Solution().reverseBetween(n1,2,4);

         System.out.println("反转链表:"+n.val+"->"+n.next.val+"->"+n.next.next.val+"->"+n.next.next.next.val+"->"+n.next.next.next.next.val);

     }

 }

 class Solution {

 public ListNode reverseBetween(ListNode head, int m, int n) {

         ListNode dummy=new ListNode(0);

         dummy.next=head;

         ListNode pre=dummy;

         ListNode current=head;

         for(int i=1;i<=m-1;i++){

             pre=current;

             current=current.next;

         }

         ListNode then=null,then_next=null;

         if(current!=null)

             then=current.next;

         if(then!=null)

             then_next=then.next;

         for(int j=m;j<n;j++){

             then.next=current;

             current=then;

             then=then_next;

             if(then_next!=null)

                 then_next=then_next.next;

         }

         pre.next.next=then;

         pre.next=current;

         return dummy.next;

     }

 }

 class ListNode {

     int val;

     ListNode next;

     ListNode(int x) { val = x; }

     }

程序结果：

巴特西

【LeetCode92】Reverse Linked List II★★

最新文章

热门文章