leetcode-hot-100-20230924

148. 排序链表（Java实现）

/**
 * 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 sortList(ListNode head) {
        //思路：使用list保存，然后排序，排序之后重新创建结点即可
        if(head == null){
            return head;
        }

        //创建保存结点的list数组
        List<ListNode> keep = new ArrayList<>();
        ListNode node = head;
        while(node != null){
            keep.add(new ListNode(node.val));
            node = node.next;
        }

        //对keep列表进行升序排序
        Collections.sort(keep, new Comparator<ListNode>(){
            @Override
            public int compare(ListNode n1, ListNode n2){
                return n1.val - n2.val;
            }
        });

        ListNode resultNode = new ListNode(0);
        ListNode p = resultNode;

        for(int i = 0;i < keep.size();i++){
            p.next = keep.get(i);
            p = p.next;
        }

        return resultNode.next;
    }
}

23. 合并 K 个升序链表（Java实现）

/**
 * 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 mergeTwoList(ListNode n1, ListNode n2){
        ListNode p1 = n1;
        ListNode p2 = n2;
        ListNode resultNode = new ListNode(0);
        ListNode node = resultNode;

        while(p1 != null && p2 != null){
            if(p1.val < p2.val){
                node.next = new ListNode(p1.val);
                p1 = p1.next;
            }else{
                node.next = new ListNode(p2.val);
                p2 = p2.next;
            }
            node = node.next;
        }

        while(p1 != null){
            node.next = new ListNode(p1.val);
            p1 = p1.next;
            node = node.next;
        }

        while(p2 != null){
            node.next = new ListNode(p2.val);
            p2 = p2.next;
            node = node.next;
        }

        return resultNode.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        int length = lists.length;

        if(length == 1){
            return lists[0];
        }

        if(length == 0){
            return null;
        }

        ListNode tmp = new ListNode(0);
        tmp = mergeTwoList(lists[0], lists[1]);

        //思路：将k个list转换为每次合并两个list，然后将合并后的list与下一个list进行合并
        for(int i = 2;i < length;i++){
            //合并tmp与之后的list
            tmp = mergeTwoList(tmp, lists[i]);
        }

        //返回tmp即可
        return tmp;
    }
}

146. LRU 缓存（Java实现）

class LRUCache {

    //内部LinkedNode类
    class LinkedNode{
        //定义内部类变量
        int key;
        int value;
        LinkedNode prev;
        LinkedNode next;

        //原始的构造函数
        public LinkedNode(){

        }

        //自定义构造函数
        public LinkedNode(int key, int value){
            this.key = key;
            this.value = value;
        }
    }

    //创建Map对象，key为Integer类型变量，value为LinkedNode
    public Map<Integer, LinkedNode> keep = new HashMap<>();
    //创建记录当前keep中容量的变量
    public int size;
    //创建记录keep最大容量的变量
    public int capacity;
    //创建记录head和tail的LinkedNode变量
    public LinkedNode head;
    public LinkedNode tail;

    //初始化构造函数
    public LRUCache(int capacity) {
        //赋值给类成员变量capacity
        this.capacity = capacity;
        this.size = 0;
        //创建head和tail结点
        head = new LinkedNode();
        tail = new LinkedNode();

        //设置head和tail的指向
        head.next = tail;
        tail.prev = head;
    }

    //创建的addToHead()方法
    public void addToHead(LinkedNode node){
        node.prev = head;//这里的head头结点为两端结点，并一直保持在两端
        node.next = head.next;

        head.next.prev = node;
        head.next = node;

    }

    //创建的removeNode()方法
    public void removeNode(LinkedNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }


    //创建的moveToHead()方法
    public void moveToHead(LinkedNode node){
        //首先移除node
        removeNode(node);
        //然后增加node到链表头部
        addToHead(node);
    }

    //创建的removeTail()方法
    public LinkedNode removeTail(){
        //获得尾部结点
        LinkedNode node = tail.prev;
        //使用removeNode删除结点
        removeNode(node);
        //返回node
        return node;
    }

    //get方法
    public int get(int key) {
        LinkedNode node = keep.get(key);
        //如果不存在返回-1
        if(node == null){
            return -1;
        }

        //移动到头结点（表示最近使用的node结点）
        moveToHead(node);
        return node.value; 
    }

    public void put(int key, int value) {
        //获得当前key对应的node
        LinkedNode node = keep.get(key);
        
        //表示7个结点
        if(node == null){
            //创建值为value的新结点
            LinkedNode newNode = new LinkedNode(key, value);
            //size++
            size++;
            //放入到keep中
            keep.put(key, newNode);
            //首次添加到缓存中的，在头部
            addToHead(newNode);
            //如果size大于capacity
            if(size > capacity){
                //删除尾部结点
                LinkedNode tailNode = removeTail();
                //在缓存中删除对应的key
                keep.remove(tailNode.key);
                size--;//当前容量减1
            }
        }else{
            node.value = value;
            moveToHead(node);//将node结点移动到head头部
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

94. 二叉树的中序遍历（Java实现）

/**
 * 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 {
    //定义结果返回list列表
    List<Integer> result = new ArrayList<>();

    //定义使用递归方法遍历二叉树
    public void inorder(TreeNode node){
        if(node == null){
            return;
        }
        //按照左中右的顺序遍历
        inorder(node.left);
        //处理中间结点
        result.add(node.val);
        inorder(node.right);
    }


    public List<Integer> inorderTraversal(TreeNode root) {
        //清除result列表中的元素
        result.clear();
        inorder(root);
        return result;
    }
}

104. 二叉树的最大深度（Java实现）

/**
 * 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 int getDepth(TreeNode node){
        if(node == null){
            return 0;
        }

        //获得左子树深度
        int leftDepth = getDepth(node.left);
        //获得右子树深度
        int rightDepth = getDepth(node.right);

        int maxDepth = Math.max(leftDepth, rightDepth) + 1;

        return maxDepth;
    }


    //遍历二叉树
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }

        return getDepth(root);
    }
}

226. 翻转二叉树（Java实现）

/**
 * 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 invertTree(TreeNode root) {
        if(root == null){
            return root;
        }

        //交换左右结点
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        
        invertTree(root.left);
        invertTree(root.right);

        return root;
    }
}