链表内指定区间反转

public class Solution {

    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        if (m == n) {
            return head;
        }
        ListNode temp = head;
        
        List<ListNode> cache = new ArrayList<>(n-m+1);
        int sign = 1;
        while(head!=null){
            if(sign>=m&&sign<=n){
                cache.add(head);
            }
            head= head.next;
            sign++;
        }
        int left = 0;
        int right = cache.size()-1;
        while(left<right){
            ListNode leftNode = cache.get(left);
            ListNode rightNode = cache.get(right);
            int leftTemp = leftNode.val;
            leftNode.val = rightNode.val;
            rightNode.val = leftTemp;
            left++;
            right--;
        }
        return temp;
    }
}

利用栈

    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
       Stack stack = new Stack();
            ListNode temp = new ListNode(0);
            ListNode temp1 = temp;
            int count = 1;
            while (head != null) {
                if (count >= m && count <= n) {
                    stack.push(head);
                } else {
                    if (stack.isEmpty()) {
                        temp.next = head;
                        temp = head;
                    } else {
                        while (!stack.isEmpty()) {
                            ListNode pop = stack.pop();
                            temp.next = pop;
                            temp = pop;
                        }
                        temp.next = head;
                        temp = head;
                    }
                }
                count++;
                head = head.next;
            }
            if (!stack.isEmpty()) {
                while (!stack.isEmpty()) {
                    ListNode pop = stack.pop();
                    temp.next = pop;
                    temp = pop;
                }
                temp.next = null;
            }
            return temp1.next;
    }

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

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
        // 1.先定义两个指针start和end，分别指向前方的m位置和后方的n位置
        ListNode start = null;
        ListNode end = null;

        // 2.记录start指针的上一个结点allPre，end指针的下一个结点allPost
        ListNode allPre = head;     // 先把allPre指向head这个整个链表的起点，随着查找m可以往后移动head
        ListNode allPost = null;
        // 准备找到m和n位置对应的start和end，以及对应的allPre和allPost
        ListNode cur = head;
        for (int i = 1; cur != null; cur = cur.next, i++) {
            if (i == m) {
                start = cur;
            }
            if (i == n) {
                end = cur;
                allPost = end.next;
                break;
            }
            // 只有在i>1（让allPre落后一位）且i<m（还没找到start）时更新allPre
            if (i > 1 && i < m) {
                allPre = allPre.next;
            }
        }
        System.out.println("allPre: " + (allPre != null ? allPre.val : "null"));
        System.out.println("start: " + (start != null ? start.val : "null"));
        System.out.println("end: " + (end != null ? end.val : "null"));
        System.out.println("allPost: " + (allPost != null ? allPost.val : "null"));

        // 3.执行类似于上一题的方法，反转start和end之间的链表，返回反转后的起点newStart和终点newEnd
        ListNode newStart = end;
        ListNode newEnd = start;
        // 只有strat和end不指向同一个结点（反转区间>1）时，才有反转的必要
        if (start != end) {
            ListNode newPre = start;
            ListNode newCur = start.next;
            ListNode newNext = newCur.next;
            // 此处不用管newPre的next指向何方，因为这个newPre就是newEnd，是数组反转后的结尾，下文会令其指向allPost
            while(newCur != allPost) {
                newNext = newCur.next;
                newCur.next = newPre;
                System.out.println("结点" + newCur.val + "的反转已完成");
                newPre = newCur;
                newCur = newNext;
            }
        }

        // 4.令allPre指向newStart，令allPost指向newEnd
        // 注意allPre的边界判断！allPre可能与newEnd（start）重合！
        if (allPre == newEnd) {
            // 如果allPre 跟 newEnd（start） 是同一个结点（m=1的情况），说明start前面没有任何元素，这时可以直接移动head到链表区间反转后的起点，令head = newStart
            allPre = newStart;
            head = allPre;
        } else {
            // 否则，是正常情况，令allPre指向newStart，从newStart到newEnd是反转区间
            allPre.next = newStart;
        }
        newEnd.next = allPost;
        System.out.println("newEnd结点" + newEnd.val + "的下一个结点allPost是" + (allPost != null ? allPost.val : "null"));
        System.out.println("allPre结点" + allPre.val + "的下一个结点newStart是" + (newStart != null ? newStart.val : "null"));
        System.out.println("head结点" + head.val);
        return head;
    }
}

public ListNode reverseBetween (ListNode head, int m, int n) {
    // write code here
    ListNode pre=new ListNode(0) ,p1=pre;
    pre.next=head;
    for(int i=1;i<m;i++){
        p1=p1.next;
    }
    ListNode p2=p1.next ,temp=p1.next;
    for(int i=m;i<=n;i++){
        ListNode node=p2.next;
        p2.next=p1.next;
        p1.next=p2;
        p2=node;
    }
    temp.next=p2;
    return pre.next;
}

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 root = new ListNode(-1);
  
    root.next = head;
  
    ListNode left = null;
  
    ListNode right = null;
  
    ListNode begin = root;
  
    ListNode end = root;
  
    for(int i=0;i<m;i++){
  
        left = begin;
  
        begin = begin.next;
  
    }
  
    for(int i=0;i<n;i++){
  
        end = end.next;
  
        right = end.next;
  
    }
  
    left.next = null;
  
    end.next = null;
  
    reverseNode(begin);
  
    left.next = end;
  
    begin.next = right;
  
    return root.next;

  }

  public ListNode reverseNode (ListNode head){

    if(head == null) {
  
        return null;
  
    }
  
    ListNode pre = null;
  
    ListNode next = null;
  
    while(head != null) {
  
        next = head.next;
  
        head.next = pre;
  
        pre = head;
  
        head = next;
  
    }
  
    return pre;

  }

}

import java.util.*;
public class Solution {
    public ListNode reverseBetween (ListNode head, int m, int n) {

        // dummy -> l1 -> l2 -> l3， 反转 l2

        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        // 断开
        ListNode p = dummy;
        int idx = 0;
        while ( idx < m-1 ) {
            p = p.next;
            idx ++;
        }
        ListNode l1Tail = p, l2Head = p.next;
        p.next = null;

        // 断开
        p = l2Head;
        while ( idx < n-1 ) {
            p = p.next;
            idx ++;
        }
        ListNode l3Head = p.next;
        p.next = null;

        ListNode[] headTail = reverse(l2Head);

        l1Tail.next = headTail[0];
        headTail[1].next = l3Head;

        return dummy.next;

    }
    ListNode[] reverse(ListNode head) {
        ListNode pre = null, cur = head, nxt = null;
        while ( cur != null ) {
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return new ListNode[]{pre, head};
    }
}

    // 方法一：
    public ListNode reverseBetween (ListNode head, int m, int n) {

        // 用于指向头结点，在完成反转后返回，防止头节点丢失
        ListNode dummy = new ListNode(-1);
        // next指向头节点
        dummy.next = head;
        ListNode pre = dummy;
        // 将pre移至m节点的前一个节点
        for(int i= 1;i<m;i++){
            pre = pre.next;
        }
        // 指向m节点
        ListNode cur = pre.next;
        // 初始化cur节点的下一节点
        ListNode temp = null;
        // 进行n-m次反转,反转过程中，cur节点一直不变，因为cur节点最终会位于反转链的末尾，
        // 每一次循环都完成一次将原cur链中cur节点的下一节点放至反转链的头节点位置，并与pre节点拼接的过程
        for(int i = 0;i<(n-m);i++){
            temp = cur.next;
            //cur节点指向它的下下节点,即删除pre链和cur链中的temp节点(cur的下一个节点)
            cur.next = temp.next;
            // 使temp节点指向pre节点的下一节点，即在pre节点的一下节点前拼接temp节点
            temp.next = pre.next;
            // 在pre节点后拼接temp链
            pre.next = temp;
        }
        // 如果从第一个节点开始反转，此时pre = dummy，则pre.next = temp即为dummy.next = temp，首节点会变化
        // 如果不是从第一个节点开始反转，则pre != dummy,则dummy.next =  head，而head在反转过程中未发生变化，首节点不变化
        // 这保证了dummy一直指向头结点，因此不返回head或者pre，而是返回dummy.next
        return dummy.next;
    }

    // 方法二：
    // 为什么我想的这么复杂！！！！    
    public ListNode reverseBetween2 (ListNode head, int m, int n) {    

        // 用于计数
        int count = 0;
        // 当前节点
        ListNode cur = head;
        // 反转串的头结点
        ListNode headOfReverse = null;
        // 反转串的尾节点
        ListNode tailOfReverse = null;
        // 从首节点后任意节点开始反转
        if (m > 1) {
            // 反转串前第一个不反转的节点
            ListNode node = null;
            while (count <= n) {
                count++;
                // 记录反转串的尾节点
                if (count == m) tailOfReverse = cur;
                // 开始反转
                if (count >= m && count <= n) {
                    ListNode temp = cur.next;
                    cur.next = headOfReverse;
                    headOfReverse = cur;
                    cur = temp;
                // 未开始反转时
                } else if (count<n){
                    // 记录反转串前第一个不反转的节点
                    node = cur;
                    // 当前节点后移
                    cur = cur.next;
                } 
            }
            // 拼接反转串前第一个不反转的节点与反转串
            node.next = headOfReverse;
            // 拼接反转串的尾节点与反转串后不反转的节点
            tailOfReverse.next = cur;
            // 返回原头结点
            return head;
        // 首节点开始反转
        } else {
            cur = head;
            while (count <= n) {
                count++;
                // 记录反转串的尾节点
                if (count == m) tailOfReverse = head;
                // 开始反转
                if (count >= m && count <= n) {
                    ListNode temp = cur.next;
                    cur.next = headOfReverse;
                    headOfReverse = cur;
                    cur = temp;
                }
            }
            // 拼接反转串的尾节点与反转串后不反转的节点
            tailOfReverse.next = cur;
            // 反转串的头节点成为新的头节点，返回反转串的头结点
            return headOfReverse;
        }
    
    }