啊啊啊啊啊啊啊啊code

前序遍历和中序遍历构建二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int preLen = preorder.length;
        int inLen = inorder.length;
        if (preLen != inLen)
            return null;
        // 创建一个哈希表用来存储中序遍历的信息，键为中序遍历的值，值为中序遍历的值的下标信息
        HashMap<Integer, Integer> map = new HashMap<>(preLen);
        for (int i = 0; i < preLen; i++)
            map.put(inorder[i], i);
        return buildTree(preorder, 0, preLen - 1,
                map, 0, inLen - 1);
    }

    private TreeNode buildTree(int[] preorder, int preLeft, int preRight,
            Map<Integer, Integer> map, int inLeft, int inRight) {

        if (preLeft > preRight || inLeft > inRight)
            return null;
        // 创建根节点信息
        int rootVal = preorder[preLeft];
        TreeNode root = new TreeNode(rootVal);
        int pIndex = map.get(rootVal);// 得到根在中序遍历中的下标信息
        // pIndex-1-inLeft = x-(preLeft+1)
        int x = pIndex - inLeft + preLeft;
        root.left = buildTree(preorder, preLeft + 1, x,
                map, inLeft, pIndex - 1);
        root.right = buildTree(preorder, x + 1, preRight,
                map, pIndex + 1, inRight);
        return root;
    }
}

旋转链表右移

class Solution {
    public ListNode rotateRight(ListNode head, int k) {
        if (k == 0 || head == null || head.next == null)
            return head;

        // 找到链表长度和末尾结点 
        int len = 1;
        ListNode iter = head;
        while (iter.next != null) {
            len++;
            iter = iter.next;
        }

        // 将链表团成环
        iter.next = head;

        // 找到新链表的末尾位置所在的下标
        int n = len - k % len;
        while (n-- > 0) {
            iter = iter.next;
        }

        // 断开链表
        ListNode newhead = iter.next;
        iter.next = null;
        return newhead;
    }
}

链表合并

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode temp = new ListNode(-1);

        ListNode prev = temp;   // 指向当前较小的节点

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                prev.next = list1;
                list1 = list1.next;
            } else {
                prev.next = list2;
                list2 = list2.next;
            }
            prev = prev.next;  // 更新指针
        }

        // 合并后list1和list2最多会有一个没合并完，直接将链表的末尾指针指向未完成合并的链表即可
        prev.next = (list1 == null ? list2 : list1);
        return temp.next;   // temp第一个节点无效，所以从next返回
    }

}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        return mergeKLists(lists, 0, lists.length);
    }

    // 合并从lists[i]到lists[j-1]的数组
    private ListNode mergeKLists(ListNode[] lists, int i, int j) {
        int m = j - i;// 合并的全体范围，后续用于折半
        if (m == 0)
            return null;

        if(m==1)
            return lists[i];
        ListNode mergeKListsLeft = mergeKLists(lists, i, i + m / 2);  // 左边需要合并的有序
        ListNode mergeKListsRight = mergeKLists(lists, i + m / 2, j); // 右边需要合并的有序

        return mergeTwo(mergeKListsLeft, mergeKListsRight); // 将最终结果合并
    }

    private ListNode mergeTwo(ListNode list1, ListNode list2) {
        ListNode dummp = new ListNode(-1);
        ListNode prev = dummp;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                prev.next = list1;
                list1 = list1.next;
            } else {
                prev.next = list2;
                list2 = list2.next;
            }
            prev = prev.next;
        }
        if (list1!= null)
            prev.next = list1;
        if (list2!= null)
            prev.next = list2;
        return dummp.next;
    }
}

K个一组翻折链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 求解链表的长度
        ListNode p = new ListNode(-1, head);
        int len=0;
        while (p.next != null) {
            len++;
            p = p.next;
        }

        ListNode dummy = new ListNode(0, head);
        ListNode p0 = dummy;
        ListNode pre = null;
        ListNode curr = head;
        while (len >= k) {
            // 每k组进行翻转
            for (int i = 0; i < k; i++) {
                ListNode next = curr.next;
                curr.next = pre;
                pre = curr;
                curr = next;
            }

            ListNode nxt = p0.next;
            p0.next.next = curr;
            p0.next = pre;
            p0 = nxt;
            len = len - k;
        }
        return dummy.next;
    }
}

合并区间

class Solution {
    public int[][] merge(int[][] intervals) {
        // 按照二维数组的第一位进行排序
        Arrays.sort(intervals, (p, q) -> p[0] - q[0]);
        // 创建一个可变数组作为结果值返回
        ArrayList<int[]> ans = new ArrayList<>();

        // 遍历排序好的每一个数组
        for (int[] p : intervals) {
            int m = ans.size();
            // 当前遍历到的数组的最小值<=结果数组中最后一个数组的最大值，表示有重合
            if (m > 0 && p[0] <= ans.get(m - 1)[1]) {
                ans.get(m - 1)[1] = Math.max(ans.get(m - 1)[1], p[1]);
            } else
                ans.add(p);
        }
        return ans.toArray(new int[ans.size()][]);
    }
}