题解 | #将单链表的每K个节点之间逆序#

// [1, 2, 4, 5, 6] ==> [1, 5, 4, 2, 6] 有两个降序，第一个降序的第一个数是一个错误。
// 第二个降序的第二个数是第二个错误
// [1,3,4,5,7,9] ===> [1,4,3,5,7,9] 有一个降序， 第一个数是一个错误，第二个数是第二个错误
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int rootVal = sc.nextInt();
        Node head = new Node(rootVal);
        HashMap<Integer, Node> hm = new HashMap<Integer, Node>();
        hm.put(rootVal, head);
        Node cur = null;
        for(int i = 0; i < m; i++) {
            int c = sc.nextInt();
            cur = hm.get(c);
            int l = sc.nextInt();
            int r = sc.nextInt();
            if(l != 0) {
                cur.left = new Node(l);
                hm.put(l, cur.left);
            }
            if(r != 0) {
                cur.right = new Node(r);
                hm.put(r, cur.right);
            }
        }
        Node[] errs = getErrs(head);
        for(Node item : errs) {
            System.out.print(String.valueOf(item.val)+" ");
        }
    }
    public static Node[] getErrs(Node head) {
        Node[] errs = new Node[2];
        Stack<Node> st = new Stack<Node>();
        Node cur = null;
        Node pre = null;
        while(head != null || !st.isEmpty()) {
            if(head != null) {
                st.push(head);
                head = head.left;
            } else {
                head = st.pop();
                if(pre != null && head.val < pre.val) {
                    errs[1] = errs[1] == null ? pre : errs[1];
                    errs[0] = head;  
                }
                pre = head;
                head = head.right;
            }
        }
        return errs;
    }
}
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node(int val) {
        this.val = val;
    }
}

利用栈中序遍历这棵树，然后发现降序时候，记录节点，注意！！！可能有一次降序，也有可能有两次降序，需要仔细讨论一下