第92题：反转链表II

一．问题描述

反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。

说明:

1 ≤ m ≤ n ≤ 链表长度。

示例:

输入: 1->2->3->4->5->NULL, m = 2, n = 4

输出: 1->4->3->2->5->NULL

二．解题思路

解题思路：利用链表性质进行求解，一次扫描。

步骤一：找到m的边界，将m前面一个节点用first指向，m的第一个节点用temp指向，temp的下一个节点用data指向，data的下一个节点用result指向。

步骤二：将data的下一个节点指向temp，然后将temp指向data，data指向result，

Result指向result的下一个节点。

步骤三：重复步骤二直到到达n的边界。

步骤四：将m边界节点的第一个节点指向data，m边界前一个节点指向temp。

三．执行结果

执行用时 :0 ms, 在所有 java 提交中击败了100.00%的用户

内存消耗 :34.2 MB, 在所有 java 提交中击败了87.11%的用户

四． Java代码

class Solution {

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

         if(m==n)

          {

              return head;

          }else

          {

              ListNode all=new ListNode(0);

              all.next=head;

              ListNode temp=all;

              ListNode first=null;

              for(int i=0;i<m&&temp!=null;i++)

                  {

                      first=temp;

                      temp=temp.next;

                  }

              ListNode data=temp.next;

              ListNode result=data.next;

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

                  {

                     data.next=temp;

                     temp=data;

                     data=result;

                     if(result!=null)

                     result=result.next;

                  }

                  first.next.next=data;

                  first.next=temp;    

            return all.next;

          }

    }

}

巴特西

第92题：反转链表II

最新文章

热门文章