本文共 1970 字，大约阅读时间需要 6 分钟。

题目来源

题目描述

解答一（递归）

需要两个不同指针，一个指向第 m 个结点，另一个指向第 n 个结点。一旦有了这两个指针，我们就可以不断地交换这两个指针指向结点的数据，并将两个指针相向移动，就像字符串的情况那样。然而，链表中没有向后指针，也没有下标。因此，我们需要使用递归来 模拟 向后指针。递归中的回溯可以帮助我们模拟一个指针从第n个结点向中心移动的移动过程。

class Solution {
       private ListNode left;    private boolean stop;    public ListNode reverseBetween(ListNode head, int m, int n) {
           this.left=head;        this.stop=false;        this.recurseAndRrverse(head,m,n);        return head;        }    public void recurseAndRrverse(ListNode right,int m,int n){
           if(n==1){
               return;        }        right=right.next;        if(m>1){
               this.left=this.left.next;        }        recurseAndRrverse(right,m-1,n-1);        if(this.left==right||right.next==this.left){
               this.stop=true;        }         if(!this.stop){
               int i=this.left.val;            this.left.val=right.val;            right.val=i;            this.left=this.left.next;        }    }}

解答二(迭代）

class Solution {
       public ListNode reverseBetween(ListNode head, int m, int n) {
           // Empty list        if (head == null) {
               return null;        }        // Move the two pointers until they reach the proper starting point        // in the list.        ListNode cur = head, prev = null;        while (m > 1) {
               prev = cur;            cur = cur.next;            m--;            n--;        }        // The two pointers that will fix the final connections.        ListNode con = prev, tail = cur;        // Iteratively reverse the nodes until n becomes 0.        ListNode third = null;        while (n > 0) {
               third = cur.next;            cur.next = prev;            prev = cur;            cur = third;            n--;        }        // Adjust the final connections as explained in the algorithm        if (con != null) {
               con.next = prev;        } else {
               head = prev;        }        tail.next = cur;        return head;    }}

转载地址：http://nnlzi.baihongyu.com/